共计 3424 个字符，预计需要花费 9 分钟才能阅读完成。
开篇介绍
大家好，我是 Java 最全面试题库 的提裤姐，明天这篇是数据结构与算法的第九篇，次要介绍散列技术；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。
散列表
散列法又称哈希法，它在元素的存储地位与元素关键码间建设一个确定的对应函数关系Hash（），使每个关键码与构造中的一个惟一的存储地位绝对应：Address=Hash（Rec.key） 插入时，依照此函数计算存储地位并寄存，查找时对元素的关键码进行相应的函数计算，把求得的函数值与关键码进行比对，统一则查找胜利。依照此办法结构的表构造即为散列表
散列函数的构造方法
1. 间接定址法
能够间接应用f(key)=a*key+b，这样的模式获取 value 值
2. 平方取中法
先通过关键字的平方值扩充相近值的差异，而后依据表长度取两头几位数作为散列函数值。
int Hash(int key) {
key *= key;
key /= 100;
return key%100;
}3. 除留余数法
能够应用 f(key) = key % p 的办法去计算 value 值。
4. 随机数法
抉择一个随机函数，取关键字的随机函数值为他的散列地址，即 h(key) = random(key)
抵触解决办法
1. 凋谢定制法
所谓的凋谢定址法就是一旦产生了抵触，就去寻找下一个空的散列地址，只有散列表足够大，空的散列地址总能找到，并将记录存入。
公式：hi=(h(key) + di) % m
比如说，关键字汇合为 {12, 38, 26}，表长为 12。散列函数f(key) = key mod 12。
计算 key 等于 26 的时候求余是 2。然而 2 的地位曾经有值了，那么进行接下来的操作f(36) = (f(36)+1)mod 12，这个时候就没有值了。那么就有空位了。
这个就是线性探测法。
2. 拉链法
拉链法的解决办法是，当呈现抵触的时候，会把抵触值变成一个链表加在最初面。
拉链法也有毛病，就是链表数量一旦变得很大的时候，查找的性能变得很大。jdk 的解决办法是当链表长度大于 8 的时候变成红黑树。
散列表实现
public class HashTable<K, V> {
private int size;// 元素个数
private static int initialCapacity=16;//HashTable 的初始容量
private Entry<K,V> table[];// 理论存储数据的数组对象
private static float loadFactor=0.75f;// 加载因子
private int threshold;// 阀值，能存的最大的数 max=initialCapacity*loadFactor
// 结构指定容量和加载因子的结构器
public HashTable(int initialCapacity,float loadFactor){if(initialCapacity<0)
throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);
if(loadFactor<=0)
throw new IllegalArgumentException("Illegal loadFactor:"+loadFactor);
this.loadFactor=loadFactor;
threshold=(int)(initialCapacity*loadFactor);
table=new Entry[threshold];
}
// 应用默认参数的结构器
public HashTable(){this(initialCapacity,loadFactor);
}
// 放入元素
public boolean put(K key,V value){
// 获得在数组中的索引值
int hash=key.hashCode();
Entry<K,V> temp=new Entry(key,value,hash);
if(addEntry(temp,table)){
size++;
return true;
}
return false;
}
// 增加元素到指定索引处
private boolean addEntry(HashTable<K, V>.Entry<K, V> temp,
HashTable<K, V>.Entry<K, V>[] table) {
//1. 获得索引值
int index=indexFor(temp.hash,table.length);
//2. 依据索引找到该地位的元素
Entry<K,V> entry=table[index];
//2.1 非空，则遍历并进行比拟
if(entry!=null){while(entry!=null){if((temp.key==entry.key||temp.key.equals(entry.key))&&temp.hash==entry.hash
&&(temp.value==entry.value||temp.value.equals(entry.value)))
return false;
else if(temp.key!=entry.key&&temp.value!=entry.value){if(entry.next==null)
break;
entry=entry.next;
}
}
//2.2 链接在该索引地位处最初一个元素上
addEntryLast(temp,entry);
}
//3. 若空则间接放在该地位
setFirstEntry(temp,index,table);
//4. 插入胜利，返回 true
return true;
}
// 链接元素到指定索引处最初一个元素上
private void addEntryLast(HashTable<K, V>.Entry<K, V> temp,
HashTable<K, V>.Entry<K, V> entry) {if(size>threshold)
reSize(table.length*4);
entry.next=temp;
}
// 初始化索引处的元素值
private void setFirstEntry(HashTable<K, V>.Entry<K, V> temp, int index,
HashTable<K, V>.Entry<K, V>[] table) {if(size>threshold)
reSize(table.length*4);
table[index]=temp;
// 留神指定其 next 元素，避免屡次应用该哈希表时造成抵触
temp.next=null;
}
// 扩容容量
private void reSize(int newSize) {Entry<K,V> newTable[]=new Entry[newSize];
threshold=(int) (loadFactor*newSize);
for(int i=0;i<table.length;i++){Entry<K,V> entry=table[i];
// 数组中，实际上每个元素都是一个链表，所以要遍历增加
while(entry!=entry){addEntry(entry,newTable);
entry=entry.next;
}
}
table=newTable;
}
// 计算索引值
private int indexFor(int hash, int tableLength) {
// 通过逻辑与运算，失去一个比 tableLength 小的值
return hash&(tableLength-1);
}
// 获得与 key 对应的 value 值
protected V get(K k){
Entry<K,V> entry;
int hash=k.hashCode();
int index=indexFor(hash,table.length);
entry=table[index];
if(entry==null)
return null;
while(entry!=null){if(entry.key==k||entry.key.equals(k))
return entry.value;
entry=entry.next;
}
return null;
}
// 外部类，包装须要存在哈希表中的元素
class Entry<K,V>{
Entry<K,V> next;
K key;
V value;
int hash;
Entry(K k,V v,int hash){
this.key=k;
this.value=v;
this.hash=hash;
}
}
}