hashmap的hash算法

① HashMap底层实现原理剖析

Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。

1.HashMap的数据结构：在java 中 数据结构，最基本 也就两种 一种数组 一种模拟指针。所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。数组的默认长度为16，

2.hashMap源码解析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///动态扩大容器时使用的一个hashMap

transient int size;//当前数据量

int threshold;//扩大容器时的大小 为 capacity * load factor

final float loadFactor;//使用率阀值，默认为：DEFAULT_LOAD_FACTOR

存取元素 ：调用put方法

public V put(K key, V value) { 

//判断当前table 为Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判断当前key 为null 将Null key添加到数组的第一个位置

 int hash = hash(key); //将当前key进行hash 详情见下方

 int i = indexFor(hash, table.length); //调用完hash算法后，详情见下方

 for (Entry e = table[i]; e != null; e = e.next) { //循环判断当前数组下标为Entry的实体 将当前key相同的替换为最新的值

            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); //如果key都不同 则添加Entry.详情见下方

        return null;

    }

hashMap的hash算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判断当前k是否为string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32算法得出key   的hash值

        }

        h ^= k.hashCode(); //调用key的hashCode 得出值 后使用"或"运算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。

一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。使用上述算法后 "1"就变得很均匀了。

我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity， 基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替 换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的 Entity的next，这样插入结束

    }

indexFor 返回当前数组下标 ，

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那么得到key 之后的hash如何得到数组下标呢 ？把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。

首先来解释一下为什么数组大小为2的幂时hashmap访问的性能最高？

看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 设置“bucketIndex”位置的元素为“新Entry”，// 设置“e”为“新Entry的下一个节点”

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//将当前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //将第一个就得table 复制个新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //将当前新的Entry 复制个table[bucketIndex]  旧的table[bucketIndex] 和新的table[buckIndex]之间用next关联。第一个键值对A进来，通过计算其key的hash得到的index=0，记做:table[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做: B.next = A ,table[0] = B,如果又进来C,index也等于0,那么 C.next = B ,table[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素时的过程解析

那么如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //当前key是否为null 如果为null值返回table[0]这个value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判断容量是否大于0 

 int hash = (key == null) ? 0 : hash(key); //对当前key 进行hash hash后得到一个值

 for (Entry e = table[indexFor(hash, table.length)]; //获取当前Entry 循环遍历

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

扩展问题:

1.当前我们的hashMap中越来越大的之后，"碰撞"就越来越明显，那么如何解决碰撞呢？扩容！

当hashmap中的元素个数超过数组大小capti*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题

HashMap的两种遍历方式

第一种

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以后一定要使用此种方式！

第二种

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以后尽量少使用！

归纳

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，

也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

② 面试中如何回答HashMap的工作原理

用过哪些Map类，都有什么区别，HashMap是线程安全的吗,并发下使用的Map是什么，他们
内部原理分别是什么，比如存储方式，hashcode，扩容，默认容量等。
JAVA8的ConcurrentHashMap为什么放弃了分段锁，有什么问题吗，如果你来设计，你如何
设计。
有没有有顺序的Map实现类，如果有，他们是怎么保证有序的。

hashmap的实现原理，https://blog.csdn.net/mbshqqb/article/details/79799009

下面是自己的总结:

存储结构:
里面存储的是一个entry数组，每个数组元素中的结构是一个entry链表
Entry是map中的一个静态内部类，其中的变量有:key,value,hashcocd,下一个Entry

什么是hash？
又称散列，将任意长度的输入通过散列算法转换成固定长度的输出，该输出就是散列值。这是一种压缩映射，散列值的空间通常远小于输出的空间。不同的输入有可能会散列出相同的输出，因此不能从散列值来确定唯一的输入值。这也是为什么比较两个对象不能仅仅使用hashcode方法比较的原因。

hash碰撞:
对不同的值进行hash运算生成了相同的散列值。这个是不可避免的，但是我们需要尽量的减少其带来的损失。
(1)设计好的hash算法让其尽可能的分布均匀
hashmap中的hash算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
让key的hashcode本身与它右移16位异或，是为了让它的高位与低位混合，增加低位的随机性，同时也变相保持了高位的特征

计算元素位置的算法:
int index = hash & (arrays.length-1);
那么这也就明白了为什么HashMap的数组长度是2的整数幂。比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。可以看出一个基数二进制最后一位必然位1，当与一个hash值进行与运算时，最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0，造成有些位置永远映射不上值。

对于null值的处理
hashmap是接受null值的，null值被放在数组的第一个元素当中，取出来的时候怎么处理呢？

hashmap的工作原理？
它的里面有一个Entry数组，在put时我们先根据key值计算出hashcode，进而计算出该元素在数组中的位置，将健值对封装在Map.Entry对象中，然后存储在数组中

若产生hash冲突怎么办？
每个数组元素的位置都是一个链表结构，若计算出来的hashcode相同则将元素追加到该链表当中，这是hashmap的处理方式

在取元素的时候，先计算key值对应的hashcode ，找到元素所在的位置，然后调用key的equals方法去遍历链表，最后找到元素

还有哪些解决hash冲突的方法？
开放寻址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

默认的负载因子0.75
当map的大小超过当前容量的百分之75时会进行自动扩容，会将原来的对象重新放到新的数组中

rehash 的过程是什么样子的？
说白了就是先resize，生成一个新的Entry数组，再transfer将原数组中的值重新计算index放入新的数组中，然后改变阈值为新的长度x负载因子

如果key为null，这始终会被散列到table[0]的桶中，即使是rehash的过程也是一样。非null的key也有可能会被散列到table[0]的位置，例如上图中key=“f”，而且相同的key在在不同的时间可能会被散列到不同的位置，这与rehash有关。

这个过程中容易发生什么问题呢？
容易产生条件竞争，如果在扩容的过程中put数据，会造成意想不到的结果。或者如果两个线程都触发了扩容，也会存在问题

这块有没有遇到过什么比较好的例子？

jdk1.8以后改成了红黑树，为什么？说一下红黑树的原理？

hashmap与hashtable的区别？
HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null
HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

篇幅有限，未完待续

③ HashMap是什么东西

HashMap，中文名哈希映射，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了异步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

(3)hashmap的hash算法扩展阅读：

因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。

HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。