Hash 表
Hash 表
强烈推介IDEA2020.2破解激活，IntelliJ IDEA 注册码，2020.2 IDEA 激活码
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
数组的优缺点是：寻址容易，插入和删除困难； 链表的优缺点是：寻址困难，插入和删除容易； 我们综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：左边很明显是个数组，数组的每个成员包括一个Head指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
Hash表代码展示：这里的链表直接使用了 JDK默认的链表（LinkedList），比较简单如果自己实现更好点。如果自己动链表的实现则直接使用 JDK提供的即可，不懂最好学一下链表的使用。自己实现一个链表。HashTable底层的链表 Head 指针永远指向第一个元素，如果没有元素则为空。增删改查操作都是从 Head 链表开始向下遍历即可。HashTable的查询速度非常的快，几乎是 O(1)的时间复杂度，hash就是找到一种数据内容和数据存放地址之间的映射关系。而散列法指元素特征转变为数组下标的方法。
package com.algorithms;
import java.util.Iterator;
import java.util.LinkedList;
/**
* hashTabe 哈希表的应用分析：
* 【1】HashTable是由数组和链表组成
* 【2】创建需要的数组大小
* 【3】创建链表：这里我就直接使用JDK提供的linkedList 链表了
* 【4】hashTabel中需要存放对象，我们先创建自己要存放的对象 Emp
* 【5】思想：将emp的no根据最简单的散列函数（取模）算出要存放的下标，接着将数据顺序的存放在链表中
* 【6】问题：简单的散列算法，会导致数据分布不均匀，会出现长链表。HashMap中使用key的hashcode然后在于分配大小的2的幂次数进行位运算计算
*/
public class HashTable {
//定义一个数组
private LinkedList[] arry;
//用户定义的hashTable的大小
private int size;
//构造函数，初始化数组和链表
public HashTable(int size){
this.size = size;
arry = new LinkedList[size];
//对链表进行初始化
for(int i = 0;i<size;i++){
//这里的链表我们就直接用 LinkedList 了JDK提供的，不自己手动写了。
arry[i] = new LinkedList();
}
}
//向数组中插入元素 【增】
public void put(Emp emp){
if(emp == null){
throw new IllegalArgumentException("传入的参数为空");
}
//首先获取 emp 的no对其取模
int index = emp.getNo() % size;
arry[index].add(emp);
}
//删除节点 【删】
public void del(Emp emp){
if(emp == null){
throw new IllegalArgumentException("传入的参数为空");
}
//首先获取 emp 的no对其取模
int index = emp.getNo() % size;
arry[index].remove(emp);
}
//查询链表中的元素 【列表】
public void list(){
for(int i=0;i<size;i++){
Iterator iterator = arry[i].iterator();
System.out.printf("展示第%d个链表内容：",i+1);
while(iterator.hasNext()){
Emp emp = (Emp)iterator.next();
System.out.printf(""+emp);
}
System.out.println("");
}
}
//主函数觉得不是很重要，放最后了，用来测试
public static void main(String[] args) {
HashTable hashTable = new HashTable(6);
//组装数据
hashTable.put(new Emp(1,"曹操"));
hashTable.put(new Emp(2,"刘备"));
hashTable.list();
}
}
class Emp{
private int no;
private String name;
//构造器
public Emp(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "Emp{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}