HashMap的原理

HashMap的工作原理是近年来常见的Java面试题,经常出现在中高级面试中,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。。银行更喜欢问这个问题,甚至会要求你实现HashMap来考察你的编程能力。

面试中经常可能会被问到:“知道HashTable和HashMap之间的区别吗?”、“HashMap的工作原理?”、“hash碰撞怎样发生的?”、“ConcurrentHashMap和HashMap的区别?”等一系列相关的问题。

1. HashMap的实现原理

参考版本为 JDK7,JDK8中的实现稍有不同。

HashMap是用来存储key-value键值对的一种集合,这个键值对也叫做Entry,每个Entry都是存储在一个单链表(图中的bucket)中。

HashMap的数据结构即为一个数组+多个链表,即Entry<K,V>[] table哈希表。

当向hash表中添加一个对象时,会先调用key的hashHash()方法计算出对应bucket的位置来储存Entry对象,Entry的结构如下:

static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
        ...
}

然后判断链表中是否已有对象存在,如果不存在,对象将被直接存入;

如果存在,则通过equals方法比较两个对象的key值是否相等,

如果key相等则覆盖value值,否则,使用头插法,将单链表进行纵向延伸以存储该对象,这种情况也就是所谓的“碰撞”。

2.

Comments
Write a Comment