HashMap原理

蔚落 2022-12-18 05:56 112阅读 0赞

### HashMap原理讲解 ###

*  1.HashMap的继承体系图
 *  2.Node数据结构
 *  3.底层存储结构图
 *  4.put数据原理图
 *  5.什么是Hash碰撞？
 *  6.什么是链化？
 *  7.jdk8为什么引入红黑树？
 *  8.HashMap扩容原理？

# 1.HashMap的继承体系图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center]  
这张图上最重要的接口是Map接口，AbstractMap是Map的抽象实现，HashMap接口又继承了AbstractMap，HashMap对AbstractMap已经重写得差不多了

# 2.Node数据结构 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 1]

//Node源码
    static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash;		//数据存入的地方，是K的hash值经过扰动得到的值
        final K key;		//键
        V value;			//值
        Node<K,V> next;		//碰撞之后形成链表，用于指向下一个元素
    
        Node(int hash, K key, V value, Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey()        {  return key; }
        public final V getValue()      {  return value; }
        public final String toString() {  return key + "=" + value; }
    
        public final int hashCode() { 
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) { 
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    
        public final boolean equals(Object o) { 
            if (o == this)
                return true;
            if (o instanceof Map.Entry) { 
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

# 3.底层存储结构图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 2]  
如果没有冲突，Node元素就会被放在数组中，如果产生冲突，就会形成链表，如果链表长度大于8，**同时**整个哈希表里的元素超过64个时，该链表转化为红黑树

# 4.put数据原理图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 3]

# 5.什么是Hash碰撞？ #

如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞

# 6.什么是链化？ #

碰撞后由于hash相同，所以存储在数组上的同一个位置，形成链表结构

# 7.jdk8为什么引入红黑树？ #

为了解决链化后由于链表过长而查找复杂

# 8.HashMap扩容原理？ #

以空间换时间，增大数组长度，减少了链表长度  
下图可以帮助理解，数组从16个元素扩容到32个元素，具体为什么元素要分配到这个地方需要用hash值进行计算，这里不展开  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/916023fc0ef44c32818f2c28e201b315.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/8f9ce24175464ffbb622be5d756423ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/b1fa93f8fe7a46d6a8944f5288c72209.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221122/bfb9250754e04f83aa1ee8d1780d71c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221122/5f19d18e704a4cec819d7b3cdbbee4bf.png