Keep and carry on.

数据结构：哈希表/散列表

post @ 2017-04-18

概念

​ 数组和链表对比：数组的特点是寻址容易，插入和删除困难；而链表的特点是插入和删除容易，寻址困难。

​ 散列表是时空权衡的经典例子，当我们的空间无限大时，我们可以直接使用一个很大的数组来保存键值对，并用key作为数组索引，因为空间不受限，所以我们的键的取值可以无穷大，因此查找任何键都只需进行一次普通的数组访问。反过来，若对查找操作没有任何时间限制，我们就可以直接使用链表来保存所有键值对，这样把空间的使用降到了最低，但查找时只能顺序查找。在实际的应用中，我们的时间和空间都是有限的，所以我们必须在两者之间做出权衡，散列表就在时间和空间的使用上找到了一个很好的平衡点。散列表的一个优势在于我们只需调整散列算法的相应参数而无需对其他部分的代码做任何修改就能够在时间和空间的权衡上做出策略调整。

​ 对于基于散列表实现的符号表，若我们要在其中查找一个键，需要进行以下步骤：

  • 首先我们使用散列函数将给定键转化为一个“数组的索引”，理想情况下，不同的key会被转为不同的索引，但在实际应用中我们会遇到不同的键转为相同的索引的情况，这种情况叫做碰撞。
  • 得到了索引后，我们就可以像访问数组一样，通过这个索引访问到相应的键值对。

散列表主要有两个重点问题：坐标映射和处理冲突的问题。

坐标映射主要指散列法：

1，除法散列法
最直观的一种，上图使用的就是这种散列法，公式：
index = value % 16
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

2，平方散列法
求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：
index = (value * value) >> 28
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

​ 1，对于16位整数而言，这个乘数是40503
​ 2，对于32位整数而言，这个乘数是2654435769
​ 3，对于64位整数而言，这个乘数是11400714819323198485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果你还有兴趣，就到网上查找一下“斐波那契数列”等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合，很神奇，对么？

对我们常见的32位整数而言，公式：
index = (value * 2654435769) >> 28

处理冲突的方法可以使用拉链法：

1

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Myhashtable(int initialCapacity,float loadFactor){
		if(initialCapacity<0){
			throw new IllegalArgumentException("Illegal initial capacity: "+initialCapacity);
		}
		if(initialCapacity>MAXIMUM_CAPACITY)
			initialCapacity=MAXIMUM_CAPACITY;
		if(loadFactor<=0||Float.isNaN(loadFactor))
			throw new IllegalArgumentException("Illegal load factor: "+loadFactor);
		
		int capacity=1;
		while(capacity<initialCapacity)
			capacity<<=1;
		
		this.loadFactor=loadFactor;
		threshold=(int)(capacity*loadFactor);
		table=new Entry[capacity];
	}

创建hash表的函数table的大小为大于指定initialCapacity的最小长度：table=new Entry[capacity]，其中Entry为定义的内部类，指定键-值、hash值和下一个Entry入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
static class Entry<K,V>{
		final K key;
		V value;
		Entry<K,V> next;
		final int hash;
		
		Entry(int h, K k,V v,Entry<K,V> n){
			value=v;
			next=n;
			key=k;
			hash=h;
		}
	}

put函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public V put(K key, V value){
		if(key==null)
			return putForNullKey(value);
		
		int hash=hash(key.hashCode());
		System.out.println("hashcode is "+hash);
		int i=indexFor(hash, table.length);
		
		for(Entry<K,V> e=table[i];e!=null;e=e.next){
			Object k;
			if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
				V oldValue=e.value;
				e.value=value;
				return oldValue;
			}
		}
		addEntry(hash, key, value, i);
		return null;
	}
	
	private V putForNullKey(V value) {
		// TODO Auto-generated method stub
		return null;
	}
	static int hash(int h){
		h^=(h>>>20)^(h>>>12);
		return h^(h>>>7)^(h>>>4);
	}
	
	
	static int indexFor(int h,int length){
		return h&(length-1);
	}
	
	private void addEntry(int hash,K key,V value, int bucketIndex){
		Entry<K,V> e=table[bucketIndex];
		table[bucketIndex]=new Entry<K,V>(hash, key ,value, e);
	}

三个关键函数：hash、indexFor、addEntry

散列法由hash、indexFor函数组成

hash方法为一个数学计算，indexFor运算其实是一个除法散列法并且用这种方法做效果更好。

最后是addEntry方法把元素插入到链表的头部

1
2
3
4
5
6
7
8
for(Entry<K,V> e=table[i];e!=null;e=e.next){
			Object k;
			if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
				V oldValue=e.value;
				e.value=value;
				return oldValue;
			}
		}

上边的循环主要用来找到table中的链表，如果存在该键值则返回老的value并更新value。

get函数的实现

1
2
3
4
5
6
7
8
9
10
11
public V get(Object key){
		if(key==null)
			return getForNullKey();
		int hash=hash(key.hashCode());
		for(Entry<K,V> e=table[indexFor(hash,table.length)];e!=null;e=e.next){
			Object k;
			if(e.hash==hash&&((k=e.key)==key||key.equals(k)))
				return e.value;
		}
		return null;
	}

首先还是取hash值算出来entry的入口，然后对比entry中每一个元素的key值，如果相同则返回value。

Read More
⬆︎TOP