开篇介绍
大家好，我是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; } } }