开篇介绍
大家好，我是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.拉链法
拉链法的解决方法是，当出现冲突的时候，会把冲突值变成一个链表加在最后面。
拉链法.png
拉链法也有缺点，就是链表数量一旦变得很大的时候，查找的性能变得很大。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;
}
}
}
网友评论