1.简介
哈希表是一种数据结构，它可以提供快速的插入操作和查找操作。无论数据项多少，插入和删除操作算法复杂度O（1）
实现：将值映射到数组的某个下标，在该下标处存储该值
缺点：由于其基于数组，数组创建后难以扩展。当哈希表被基本填满时，性能下降的非常严重
2.处理哈希冲突的方式
1）开放地址法
当冲突发生时，该方法通过一个函数（A）找到数组的一个空位，并将该值填入
* 线性探测（从当前下标逐个向前寻找，当碰到空位时，插入）
* 二次探测（步骤是步数的平方，线性探测的查找为x+1 x+2 x+3...二次探测则就是 x+1 x+4 x+9...）
* 再哈希法（当发生冲突时，再次创建一个哈希函数（B）来确定步长。B函数需与A函数不同，而且输出不能为0）
public void insert(int key , Item item){
int index = func1(key);
int stepSize = func2(key);
while(arr[index] != null){
index += stepSize;
index %= size;//loop
}
arr[index] = item;
}
public Item find(int key){
int index = func1(key);
int stepSize = func2(key);
while(arr[index] != null){
if(arr[index].getData() == key){
return arr[index];
}
index += stepSize;
index %= size;
}
return null;
}
public int func1(int key){
return key % size;
}
public int func2(int key){
return 5 - (key % size);
}
2）链地址法
创建一个存放单词链表的数组，数组内不直接存储单词，当发生冲突时，新的数据项直接接到这个数组下标所指的链表中
代码如下所示：
public class HashTableDemo {
private SingleLinkDemo[] arr;
private int size;
public HashTableDemo(int size) {
this.size = size;
arr = new SingleLinkDemo[size];
for (int i = 0; i < size; i++) {
arr[i] = new SingleLinkDemo();
}
}
public void insert(String data){
int key = hashFunc(data);
arr[key].insertFirst(data);
}
public void delete(String data){
int key = hashFunc(data);
arr[key].delete(data);
}
public Node find(String data){
int key = hashFunc(data);
return arr[key].find(data);
}
public int hashFunc(String data){
return data.hashCode() % size;
}
}
