HashMap数据结构与算法

爱被打了一巴掌 2022-12-21 15:49 112阅读 0赞

**目录**

HashMap的特点

HashMap JDK1.8以前（链表解决hash碰撞-冲突）

HashMap JDK1.8以后(红黑树-二叉树解决hash碰撞)

为什么JDK1.8不使用AVL树而使用红黑树？

--------------------

# HashMap的特点 #

数组\[Entry\]、链表\[Entry\[\]\]、红黑树(jdk1.8 链表长度大于8时触发)

*  快速存储(put)
 *  快速查找(时间复杂度O(1))
 *  可伸缩(loadFactor=0.75, default size=16 ，2倍扩容：16，16\*0.75->32，32\*0.75->64，64\*0.75->128.....)
 *  非线程安全(put 、remove等都是普通方法，而HashTable 方法都通过synchronized关键字处理)

/* ---------------- Public operations -------------- */
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and load factor.
         *
         * @param  initialCapacity the initial capacity
         * @param  loadFactor      the load factor
         * @throws IllegalArgumentException if the initial capacity is negative
         *         or the load factor is nonpositive
         */
        public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        /**
         * Constructs a new <tt>HashMap</tt> with the same mappings as the
         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified <tt>Map</tt>.
         *
         * @param   m the map whose mappings are to be placed in this map
         * @throws  NullPointerException if the specified map is null
         */
        public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

**HashMap最经典的问题->Hash冲突：**

Hash冲突：不同的对象算出来数组下标是相同的（桶slot的概念）

单向链表：用于解决Hash冲突的方案,加入一个next记录下一个节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jvb255YQ_size_16_color_FFFFFF_t_70][]

# HashMap JDK1.8以前（链表解决hash碰撞-冲突） #

public V put(K key, V value) {  
            if (key == null)  
                return putForNullKey(value);  
            int hash = hash(key.hashCode());  
            int i = indexFor(hash, table.length);  
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
                Object k;  
                //判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。  
                //如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。  
                //Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。  
                //系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），  
                //那系统必须循环到最后才能找到该元素。  
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                    V oldValue = e.value;  
                    e.value = value;  
                    return oldValue;  
                }  
            }  
            modCount++;  
            addEntry(hash, key, value, i);  
            return null;  
        }

# HashMap JDK1.8以后(红黑树-二叉树解决hash碰撞) #

/**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
        /**
         * Implements Map.put and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        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;
            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;
                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;
        }

# 为什么JDK1.8不使用AVL树而使用红黑树？ #

**[AVL树][AVL]本质上还是一棵二叉搜索树，它的特点是：**

*  1.本身首先是一棵二叉搜索树。
 *  2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
 *  本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）

红黑树和AVL树都是**最常用的平衡二叉搜索树**，它们的查找、删除、修改都是O(lgn) time

AVL树和红黑树有几点比较和区别：  
（1）AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。  
（2）红黑树更适合于插入修改密集型任务。  
（3）通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。

**总结**：  
（1）AVL以及红黑树是高度平衡的树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作时完成的旋转操作次数。  
（2）两种实现都缩放为a O(lg N)，其中N是叶子的数量，但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。另一方面，插入和删除方面，AVL树速度较慢：需要更高的旋转次数才能在修改时正确地重新平衡数据结构。  
（3）在AVL树中，从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中，差异可以是2倍。  
（4）两个都给O（log n）查找，但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡（尽管可能需要检查O（log n）节点以确定旋转的位置）。旋转本身是O（1）操作，因为你只是移动指针。

--------------------

参考：[https://blog.csdn.net/21aspnet/article/details/88939297][https_blog.csdn.net_21aspnet_article_details_88939297]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jvb255YQ_size_16_color_FFFFFF_t_70]: /images/20221120/c74913cdb2484c2f951557edf4b7d7b6.png
[AVL]: https://baike.baidu.com/item/AVL%E6%A0%91/10986648?fr=aladdin
[https_blog.csdn.net_21aspnet_article_details_88939297]: https://blog.csdn.net/21aspnet/article/details/88939297