java基础：14.5 散列 -- HashMap的手动实现_hashmap表示多项式

java.util.Map 接口
可以使用三个具体的类来创建一个映射表: HashMap 、LinkedHashMap 、TreeMap.

java.util.HashMap 使用散列实现
java.util.LinkedHashMap 使用LinkedList
java.util.TreeMap 使用红黑树。
 

1 散列的基本概念

1. 回顾一下映射表(map) ：键Key - 值Value 。又称为字典( dictionary)、散列表、( hash table) 或者关联数组
   (associate array) 。

2. 散列非常高效。

3. 使用散列将耗费O(1)时间来查找、插入以及删除一个元素。类比之前的学过的数组，数组通过索引获得元素，所以此处考虑：把键映射到一个索引上

4. 散列使用一个散列函数，将一个键 映射到一个索引上。

5. 存储了值Value的数组称为散列表(hash table) 。

6. 将键映射到散列表中的索引上的函数称为散列函数(hash function) 。
   散列函数从一个键Key获得索引，并使用索引来获取该键的值。

7. 散列( hashing) 是一种无须执行搜索，即可通过从键得到的索引来获取值的技术。
    

2 散列函数、散列码

典型的散列函数首先将搜索键转换成一个称为散列码的整数值，然后将散列码压缩为散列表中的索引。

Java 的根类 Object具有 hashCode 方法，该方法返回一个整数的散列码。默认的，该方法返回一个该对象的内存地址。hashCode 方法的一般约定如下:

1. 当equals 方法被重写时，应该重写hashCode 方法，从而保证两个相等的对象返回同样的散列码。
2. 程序执行中，如果对象的数据没有被修改，则多次调用hashCode 将返回同样的整数。
3. 两个不相等的对象可能具有同样的散列码，但是应该在实现hashCode 方法时避免太多这样的情形出现。

byte 、short 、int 、char 类型：对这几个类型的搜索键而言，简单地将它们转型为int 。因此，这些类型中的任何一个的不同搜索键将有不同的散列码。

float：对于float 类型的搜索键，使用 Float.floatToIntBits(key) 作为散列码。注意，floatToIntBits(float f) 返回一个int 值，该值的比特表示和浮点数f 的比特表示相同。因此，两个不同的float 类型的搜索键将具有不同的散列码。

long：不能简单地将其类型转换为int ，因为所有前32 比特不同的键将具有相同的散列码。考虑到前32 比特，将64 比特分为两部分，并执行 异或操作 将两部分结合。这个过程称为 折叠 int hashCode = (int)(key ^ (key >> 32)); >>为右移操作

字符串String类型的散列码：
一个比较直观的方法是将所有字符的Unicode 求和作为字符串的散列码，如果搜索键包含同样字母，将产生许多冲突。
一个更好的方法是 考虑字符的位置 ，然后产生散列码。称为多项式散列码。

=

实验显示， b 的较好的取值为31 ， 33 ， 37 ， 39 和41。String 类中，hashCode 采用b 值为31 的多项式散列码计算被重写。
 

3 压缩散列码

键的散列码可能是一个很大的整数，超过了散列表索引的范围，因此需要将它缩小到适合索引的范围。假设散列表的索引处于0 到N-1 之间。将一个整数缩小到0 到N-1 之间的最通常的做法是使用 h(hashCode) = hashCode % N

保证索引均匀扩展，选择N 为大于2 的素数。

理想的，应该为N 选择一个素数。然而，选择一个大的素数将很耗时。Java API 为 java.util.HashMap 的实现中， N 设置为一个2 的幂值。这样的选择具有合理性。当N 为2 的幂值时，上式与这个一样： h(hashCode) = hashCode & ( N - 1 ) .
&操作符比%操作符执行快许多。

为了保证散列码是均匀分布的， java.util.HashMap 的实现中采用了 补充的散列函数与主散列函数一起使用 。该函数定义为:

private static int supplementalHash(int h){
   
	h ^= ( h >>> 20 ) ^ (h >>> 12);
	return h ^ (h >>>7 ) ^ (h >>> 4);
1
2
3
4

^ 和>>>是比特的异或和无符号右移操作

完整的散列函数如下定义:

h(hashCode) = supplementalHash(hashCode) % N
1

这个与以下式子一样:

h(hashCode) = supplementalHash(hashCode) & (N - 1)
1

4. 地址冲突

当两个键映射到散列表中的同一个索引上，会冲突发生！通常，有两种方法处理冲突：开放地址法、链地址法。
 

4.1 开放地址法

开放地址法( open addressing) 是在冲突发生时，在散列表中找到一个开放位置的过程。
开放地址法有几个变体：线性探测、二次探测和再哈希法。

****

线性探测
当插入一个条目到散列表中发生冲突时，线性探测法( linear probing) 按顺序找到下一个可用的位置。例如，如果冲突发生在hashTable[k % N] ，则检查hashTabl e [(k+1) % N]是否可用。如果不可用，则检查hashTable[(k+2) %N]，以此类推，直到一个可用单元被找到。
(当探测到表的终点时，则返回表的起点。因此，散列表被当成是循环的。)

散列表中的每个单元具有三个可能的状态:被占的、标记的或者空的。

线性探测法容易导致散列表中连续的单元组被占用。每个组称为一个簇(cluster ) 。每个簇实际上成为在获取、添加以及删除一个条目时必须查找的探测序列。当簇的大小增加时，它们可能合并为更大的簇，从而更加放慢查找的时间。这是线性探测法的一个较大的缺点。

二次探测法
二次探测法( quadratic probing) 可以避免线性探测法产生的成簇的问题。二次探测法则从索引为 (k + j^2) %N 位置的单元开始审查，其中 j >= 0 。即 k%N ， ( k + 1) %N , (k+4 ) %N, (k+9) %N， 以此类推.。。。

二次探测法避免了线性探测法的成簇问题，但是有自己本身的成簇问题，称为二次成簇( seconda叩clustering); 即在一个被占据的条目处产生冲突的条目将采用同样的探测序列。

线性探测法可以保证只要表不是满的， 一个可用的单元总是可以被找到用于插入新的元素。然而， 二次探测法不能保证这个。

再哈希法
另外一个避免成簇问题的开放地址模式称为再哈希法( double hasbing ) 。

从初始索引k开始，线性探测法和二次探测法都对k 增加一个值来定义一个搜索序列。对于线性探测法来说增量为1 ，对于二次探测法来说增量为f。这些增量都独立于键。

再哈希法在键上应用一个 二次散列函数h' (key) 来确定增量， 从而避免成簇问题。
具体来说，再哈希法审查索引为 (k+ j*h' (key)) %N处的单元，其中 j >= 0 ，即 k%N ， (k+h’ (key)) %N , (k+2* h’ (key)) %N,
(k+3* h’ (key)) %N， 以此类推。

例如，让一个大小为11 的散列表的主散列函数h 和二次散列函数h’ 如下定义:
h(key) = key % 11 ;
h’(key) = 7 - key % 7;
 

4.2 链地址法

链地址法将具有同样的散列索引的条目都放在一个位置，而不是寻找一个新的位置。链地址法的每个位置使用一个桶来放置多个条目。可以使用数组， ArrayList 或者LinkedList 来实现一个桶。

 

5. 装填因子

装填因子( load factor) 衡量一个散列表有多满。如果装填因子溢出，则增加散列表的大小，并重新装载条目到一个新的更大的散列表中。这称为再散列。

当λ 增加时，冲突的可能性增大。研究表明，对于开放地址法而言，需要维持装填因子在0.5 以下，而对于链地址法而言，维持在0.9 以下。

将装填因子保持在一定的阔值下对于散列的性能是非常重要的。Java APl 中java.util.HashMap类的实现中，采用了阔值0.75 。一旦装填因子超过阈值，则需要增加散列表的大小，并将映射表中所有条目再散列( rehash) 到一个更大的散列表中。注意需要修改散列函数，因为散列表的大小被改变了。由于再散列代价比较大，为了减少州现再散列的可能性应该至少将散列表的大小翻倍。即使需要周期性的再散列，对于映射表来说散列依然是一种高效的实现。
 

6. 手写HashMap

（使用 链地址法 来实现映射表）
首先，参照java.util.Map 设计自定义的Map接口，接口命名MyMap，集体类命名MyHashMap。

package ReWrite;
public interface MyMap<K,V> {
   
	
	public void clear();
	public boolean containsKey(K key);
	public boolean contansVaule(V value);
	public java.util.Set<Entry<K,V>> entrySet();
	public V get(K key);
	public boolean isEmpty();
	public java.util.Set<K> keySet();
	public V put(K key,V value);
	public void remove(K key);
	public int 
1
2
3
4
5
6
7
8
9
10
11
12
13