Map的实现原理

2018-09-18 本文已影响19人 ae12

https://blog.csdn.net/justloveyou_/article/details/62893086
数组：寻址容易，插入删除难
链表：插入删除容易，寻址难

Map 底层：数组，数组的每一项都是一个链表

hashmap.png

负载因子：loadFactor: 一个散列表的空间使用程度
扩容阀值：thershold :它的值=HashMap容量* 负载因子
// map 底层实现仍是数组，只是数组的每一项都是一条链表
table =new Entry[ DEFALT_INITIAL_CAPACITY];

每次new hashmap 时候都会初始化一个Entry 类型的数组；
Entry 定义：

static class Entry<K,V> implements Map.Entry<K,V> {

    final K key;     // 键值对的键
    V value;        // 键值对的值
    Entry<K,V> next;    // 下一个节点
    final int hash;     // hash(key.hashCode())方法的返回值

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {     // Entry 的构造函数
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    ......

}

Entry是map的内部类，定义了key value等，Entry 哈希表所存储的元素的具体形式

5.存取方法
保持key唯一，需要比较，如果是用equal 效率较低，时间复杂度O（n)；哈希内部有个哈希表管理元素，哈希算法现快速存取：通过key.hashcode 获得哈希码，查对应的桶位置即bucketIndex,如果有哈希冲突，就会取出bucketIndex桶内所有元素，并通过hashcode和 equal 逐个比较看是否存在key,存在替换，不存在，存储到这个桶里

对NULL键的特别处理：putForNullKey()

    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        // 若key==null，则将其放入table的第一个桶，即 table[0]
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {   
            if (e.key == null) {   // 若已经存在key为null的键，则替换其值，并返回旧值
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;        // 快速失败
        addEntry(0, null, value, 0);       // 否则，将其添加到 table[0] 的桶中
        return null;
    }

if key ==null ,put in bucketIndext==0 ;
the key==null is the only one in the hashmap

7.hashmap中哈希策略（即hash算法）

在同一个版本的Jdk中，HashMap、HashTable以及ConcurrentHashMap里面的hash方法的实现是不同的。再不同的版本的JDK中（Java7 和 Java8）中也是有区别的。

hash() 算法对 key的hashcode 重新计算
indexFor（）生成Entry 数组对应的位置

int hash =hash(key.hashcode);
//hash在桶中的位置
int i =indexFor(hash,table.length)

先看下 hash算法的实现：
HashMap In Java 7

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

h & (length-1)什么意思呢？ hash值与hashMap的(length-1)做了&运算,取模计算（%） ,得到位于区间[0，length-1]的一个值。特别地，这个值分布的越均匀， HashMap 的空间利用率也就越高，存取效率也就越好。
为什么用&运算，而不是“%”？因为在javaz中，&运算是直接对内存数据操作，而不需要转为十进制，效率更高。

位运算(&)来实现取模运算(%)呢？这实现的原理如下：

X % 2^n = X & (2^n – 1)

2^{n表示2的n次方，也就是说，一个数对2}n取模 == 一个数和(2^n – 1)做按位与运算。

假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 = 7 ，即0111。

此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。

从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。

上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。

6 % 8 = 6 ，6 & 7 = 6

10 & 8 = 2 ，10 & 7 = 2

&=%.png

所以，只要保证hashmap长度是2的倍数，就可以实现上述的&运算 =%；
实际上，hashmap的长度的确是2的倍数，初始值是16，之后每次扩容都是原来的2倍

总结：hashmap在put() get() 时候，为了保证key的唯一性，先去查找是否已经存在key,查找方法就是通过int h= hash(key.hashCode) 得到一个int值 h,然后indexFor(h)
h&(length -1) 得到在链表数组的位置。

hash冲突：
即2个键值不同但是和（length -1）进行相与后相同，则产生冲突

hash冲突.png

主要是高位不同、地位相同造成的冲突，举个例子：
如果HashTable的大小为16，
length -1 =15 二进制：“00000000000000000000000000001111”
一个hashCode:
“1011000110101110011111010011011”
按位与算（都为1时，才=1）如下图：

按位与算.png

那么如何解决这种冲突呢，来看下Java是如何做的。其中的主要代码部分如下：

h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

意义：主要是对hashCode进行扰动，将高位、地位的特征结合，使得高位或是低位的变化都会对最终结果产生影响，从而降低产生哈希冲突的概率。
哈希：就是根据 hashCode 得到hashMap 数组所在桶的位置。

举例说明，扰乱解决冲突：
key1的hashCode是11280384，用16进制表示是0x0AC20000
key2的hash是1568768，用16进制表示是0x017F0000

如果不进行扰动，直接用hashCode来计算key在HashMap的table[]中的index：//HashMap的indexFor源码
static int indexFor(int h, int length) {
return h & (length-1);
}
假设此时table[]的length是16，那么对于key1来说就是0AC20000 & 0000000F = 0对于key2来说017F0000 & 0000000F = 0也就是说key1和key2的存储位都是0，发生了hash冲突。

加入扰动函数之后：0AC20000 >>> 20 = 000000AC0000 1010 1100 0010 0000 0000 0000 0000 右移20位 = 0000 0000 0000 0000 0000 0000 1010 11000AC20000 >>> 12 = 0000AC20000000AC ^ 0000AC20 = 0000AC8C0AC20000 ^ 0000AC8C = 0AC2AC8C
扰动函数的目的是把hashcode的高低位混在一起，让高位发生变化时，低位同时也发生变化。
接下来又进行了一些更多的扰动计算：
0AC2AC8C >>> 7 = 001585590AC2AC8C >>> 4 = 00AC2AC80AC2AC8C ^ 00158559 ^ 00AC2AC8 = 0A7B031D所以对于key1来说，扰动完成后的hash是0A7B031D而key2进行相同的扰动计算后，hash是016A18B6这样key1的存储位是13，key2是6，没有发生hash冲突。

在java8中这个扰动函数被简化了：
h = h ^ (h >>> 16)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

只简单地把hashCode的高16位移动到低16位后与自身进行异或。
（https://www.zhihu.com/question/51784530）

HashTable In Java 7
在线程安全的 HashTable中，其hash的实现：

  hash = key.hashCode();
   index = (hash & 0x7FFFFFFF) % tab.length;

可见，和HashMap的“&”不同的是，直接取模“%”

1.为何把hash值和0x7FFFFFFF做一次按位与操作呢？

Because:

0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111 : all 1 except the sign bit.
(hash & 0x7FFFFFFF) will result in a positive integer.
(hash & 0x7FFFFFFF) % tab.length will be in the range of the tab length.
哈哈，说人话就是
为了保证得到的index的第一位为0，也就是为了得到一个正数。因为有符号数第一位0代表正数，1代表负数。

HashTable采用简单的取模是有一定的考虑在的。这就要涉及到HashTable的构造函数和扩容函数了。由于篇幅有限，这里就不贴代码了，直接给出结论：

HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。

也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。

由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。（这个是可以证明出来的，由于不是本文重点，暂不详细介绍，可参考：http://zhaox.github.io/algorithm/2015/06/29/hash）

2.关于hash函数为什么要选择对素数求余?
一组均匀分布的key，其中同m公约数为1的那部分，余数后在[0,m-1]上还是均匀分布的，但同m公约数不为1的那部分，余数在[0, m-1]上就不是均匀分布的了。把m选为素数，正是为了让所有key同m的公约数都为1，从而保证余数的均匀分布，降低冲突率。
例子：一组key值 12、5、7、16、22 同m=5公约数分别为2、1、1、3、4
同m公约数不为1的那部分，余数是0、2
但同m公约数不为1的那部分，余数是 2、2、1可见不是均匀分布的；

ConcurrentHashMap

ConcurrentHashMap In Java 8
Java 8 里面的求hash的方法从hash改为了spread。实现方式如下：

static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

Map的实现原理

猜你喜欢

热点阅读