Java中的哈希表、HashMap、HashTable

所谓哈希表（HashTable，又叫散列表），是存储键值对Key-value)的表，之所以不叫它Map(键值对一起存储一般叫做Map)，是因为它下面的特性：它能把关键码(key)映射到表中的一个位置来直接访问，这样访问速度就非常快。其中的映射函数称为散列函数(Hash function)。

1) 对于关键字key, f(key)是其存储位置，f则是散列函数

2) 如果key1 != key2 但是 f(key1) == f(key2),这种现象称为冲突(collison)。冲突不可避免，这是因为key值无限而表容量总是有限。我们追求的是对任意关键字，散列到表中的地址概率是相等的，这样的散列函数为均匀散列函数。

散列函数有多种 ：
× 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）
× 数字分析法
× 平方取中法
× 折叠法
× 随机数法
× 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
可以想像，当表中的数据个数接近表的容量大小时，发生冲突的概率会明显增大，因此，在“数据个数/表容量”到达某个比例的时侯，需要扩大表的容量，这个比例称为“装填因子”(load factor).
解决冲突主要有下面两类方法：
× 分离链接法，就是对hash到同一地址的不同元素，用链表连起来，也叫拉链法
× 开放定址法，如果地址有冲突，就在此地址附近找。包括线性探测法，平方探测法，双散列等 。

然后我们来看看Java的HashTable的实现：

1
2
 
private transient Entry[] table;//Entry数组

 

1
2
3
4
5
6
7
private static class Entry<K,V> implements Map.Entry<K,V> {
   int hash;
   K key;
   V value;
   Entry<K,V> next; // Entry此处表明是个单链表
   ...
}

我们可以使用指定数组大小、装填因子的构造函数，也可以使用默认构造函数，默认数组的大小是11，装填因子是0.75.

1
2
3
4
5
6
public Hashtable(int initialCapacity, float loadFactor) {
   ...
}
public Hashtable() {
   this(11, 0.75f);
}

当要扩大数组时，大小变为oldCapacity * 2 + 1，当然这无法保证数组的大小总是素数。
来看下其中的元素插入的方法，put方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public synchronized V put(K key, V value) {
// Make sure the value is not null
   if (value == null) {
      throw new NullPointerException();
   }

// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
   for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
      if ((e.hash == hash)  && e.key.equals(key)) {
          V old = e.value;
          e.value = value;
          return old;
      }
   }
}

Java中Object类有几个方法，其中一个是hashCode(), 这说明Java中所有对象都具有这一方法，调用可以得到对象自身的hash码。对表的长度取余得址，并在冲突位置使用链表。
HashMap与Hashtable的功能几乎一样。但HashMap的的初始数组大小是16而不是11，当要扩大数组时，大小变为原来的2倍，默认的装填因子也是0.75. 其put方法如下，对hash值和index都有更改：

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
40
41
public V put(K key, V value) {
   if (key == null)
     return putForNullKey(value);
   int hash = hash(key.hashCode());
   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;
           e.recordAccess(this);
           return oldValue;
       }
   }

   modCount++;
   addEntry(hash, key, value, i);
   return null;
}

/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
   return h & (length-1);
}

HashMap底层维护一个数组，我们向HashMap中所放置的对象实际上是存储在该数组当中。

当向HashMap中put一对键值时，它会根据key的hashCode值计算一个位置，该位置就是此对象准备往数组中存放的位置。

如果该位置没有对象存在，就将此对象直接放进数组中，如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找（Entry类有一个Entry类型的next成员变量，指向了该对象的下一个对象），如果此链上有对象的话，再去使用equals方法进行比较，如果对此链上的某个对象的equals方法比较为false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对象的后面。

除非注明，饮水思源博客文章均为原创，转载请以链接形式标明本文地址

本文地址：http://www.alonemonkey.com/java-hash.html

本文链接：http://www.alonemonkey.com/java-hash.html