search

MicroKibaco / CrazyDailyQuestion

每日一问: 水滴石穿，聚沙成塔，坚持数月, 必有收获~
35 stars 1 forks source link

2019-08-19 : 说说HashMap的底层原理与存储过程以及与HashTable,TreeMap,ConcurrentHashMap,LinkedHashMap, WeakHashMap区别? #15

Open MicroKibaco opened 5 years ago

SeniorDoctorHui commented 5 years ago

HashMap

HashMap底层是使用数组加链表实现的，所以我们说HashMap是散列链表。 添加元素时，首先通过key进行哈希计算，计算出该元素在节点数组的下标，如果该数组下标没有元素，则将该节点放到该位置 如果该节点已有元素，则遍历该元素与其后面的节点，如果发现有和要添加节点的key一样的节点，则替换该节点的值。若最终未发现，则将要添加的节点放到数组当前下标处，next指向原先放在此下标位置的节点 当然这些操作之前，还需要判断table数组是否需要扩容操作。 HashMap实现了Map的全部方法，它有以下特点： key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法 允许空键和空值 元素是无序的，而且顺序会不定时改变 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置） 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）

HashTable

除了不允许Null key和Null Value并且同步，其他均和HashMap一致

LinkedHashMap

LinkedHashMap是HashMap的子类。它通过双向列表来保证了添加的元素的有序性。它有以下几个特点： 1 双向链表+哈希表 2 线程不安全 3 允许空的键或者值 4 有序（插入排序和访问排序）

MicroKibaco commented 5 years ago

简介

底层源码

待分析~

存储过程

  HashMap在1.7的基础上引入了 红黑树,首先针对接受需要的存储键值对(k,v)标记为x,然后再使用hashCode根据键计算hash值,这也是与JDK1.7的主要区别,然后再根据数组计算hash的下标位,如果发生hash冲突?即该位置之前存储过数据,当前节点数据结构是否为红黑树 或者 链表,如果是链表结构,在链表末尾插入数据,如果是红黑树,在红黑树插入数据,整个存储过程结束

巧妙的地方

   1.8的 扩容机制,新元素存储机制提高了效率

参考资料

Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？

pioneerz commented 5 years ago

参考：https://blog.csdn.net/bjstyle/article/details/78221429

skylarliuu commented 5 years ago

底层原理

存储过程

1. put方法添加元素

注意： HashMap在添加第一个元素时才会创建数组。

put方法分为三种情况：

2. get方法查找

3. resize扩容

resize 方法兼顾两个职责，创建初始存储表格，或者在容量不满足需求的时候，进行扩容。

对比

zhengjunke commented 5 years ago

put():在新增元素时，先通过传入的key进行哈希计算，然后得到该元素在节点数组的位置，如果该数组对应位置没有该元素，则将该节点放到该位置； 如果该位置存在该元素，则遍历该元素与其后面的节点，如果发现有和要添加节点的key一样的节点，直接替换该节点的值。若最终未发现，则将要添加的节点放到数组当前位置，然后next指向该位置的下一个节点； get():先定位到数组元素，再遍历该元素处的链表; 确定数组index：hashcode % table.length取模; 如果两个key拿到的index相等：Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。

TreeMap：通常比HashMap要慢，与使用TreeSet一样，TreeMap时一种创建有序列表的方式。树的行为时：总是保证有序，并且不必进行特殊的排序。如果使用Map，第一选择是HashMap，如果要求Map始终保持有序，可以选择TreeMap； LinkedHashMap：在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表（以保持插入顺序）。正是由于这个列表，使得其迭代速度更快。

JDK1.7中HashMap的数据结构是数组+链表； JDK1.8引入了红黑树，原因：解决发生哈希碰撞后，链表过长从而导致索引效率慢的问题；应用场景：当链表长度大于8时，该链表转换成红黑树。

gys0000 commented 5 years ago

参考的博客Java中HashMap的实现原理 HashMap底层是数组加链表的数据结构。

我们知道hash是通过某种算法，给一个对象计算出一个标志。我们在寻找这个对象的时候可以使用这个标志去寻找。扔物线老师讲过这个，我就不絮叨了。

上边两行字怎么那么大。。。奇怪，没加md的标题字符啊 我下边大概说一下HashMap的存储： 开始之前要知道hashMap中是有一个数组来存放key-value数据的。

开始

首先我们调用HashMap.put(key,value)的方法； 接着我们通过一个算法将key值转换成一个int值temp，然后我们查看数组下标为temp的数据是不是存在，如果不存在，我们直接讲key-value存到数组中，下标就是通过hash算法对key计算出来的temp值； 如果数组中temp下标中有数据怎么办呢？那说明之前存过一个可能是同样key的数据。为什么是可能相同呢？因为通过hash计算两个不相同的key，有可能得到一个相同的temp。那么我们就需要使用equals方法计算当前数组中存在的key和我要存的key是不是一样的

其实到这里我们可以发现，链表的作用其实是很小的，但是也很必要，他就是为了防止hash算法的可能会重复的特性备用的数据结构。 这其中，数组才是最主要用到的数据结构，通过hash算法计算key得到的hash值temp，我们可以很快的从数组中得到我们需要的数据，这样查询大大提高了效率。 以上我们还能得到一个结论，就是我们计算出来的temp不可能是连续的，那就是说hashMap的数据也不可能是连贯性的。

结束

以上是我看源码连蒙带猜，加看博客得出的个人理解结论，其实源码中的put方法还有几处困扰我的点，暂时还没有找到答案。但是大致的思路应该就是这样，中间我省掉了一步

if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

的讲解，这个我接下来再琢磨一下。 看源码还挺有意思，可是我基础的知识太薄弱了，中间好多都会卡壳。接下来有时间我把获取数据的源码再看一下，然后放上来给自己公开处刑。。。

看这一段源码我的几个问题，放上来大家帮我看下

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
       //1.tab[i = (n - 1) & hash]这一步没搞懂，这一步是很关键的一个验证步骤，但是内部做了什么我不太清楚
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //2.这是被我省掉的一步，应该就是上边小伙伴说的红黑树(这个有点懵逼，要看一下)
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
liu1813565583 commented 5 years ago

我说说自己的看法吧：使用最多的是HashMap。

HashMap里面存入的键值对在取出时没有固定的顺序，是随机的。一般而言，在Map中插入、删除和定位元素，HashMap是最好的选择。

在使用多线程时，考虑线程安全，优先使用HashTable。

由于TreeMap实现了SortMap接口，能够把它保存的记录根据键排序，因此，取出来的是排序的键值对，如果需要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同，那么用LinkedHashMap可以实现，它还可以按读取顺序排列。