Java中HashMap集合存取原理

我会带着你远行 2023-02-28 04:12 19阅读 0赞

**关于HashMap集合：**

1、HashMap集合底层是哈希表（散列表）的数据结构。

线程安全集合：

*  HashMap是非线程安全的。
 *  List中的Vector是线程安全的。
 *  Map中的Hashtable及其子类Properties是线程安全的。

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

**2、哈希表是一个怎样的数据结构呢？**

哈希表是一个一维数组和多个单向链表的结合体。

**数组：在查询方面效率很高，在随机增删方面效率很低。**  
**单向链表：在随机增删方面效率很高，在查询方面效率很低。**

哈希表将以上的两种数据结构联合在一起，充分发挥它们各自的优点。

哈希表是一个特殊的一维数组，特殊在每个元素存储的是一个单向链表。

数组中元素存的是单向链表，只需要存每个链表的头结点即可。

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

3、掌握哈希表的存储和取出的原理：

**（1）存储的原理**：调用map.put(k, v)方法。

*  第一步：先将k, v封装成Node节点对象。
 *  第二步：底层调用k类重写之后的hashCode()方法，得出k的int型哈希值。
 *  第三步：拿到k的哈希值，通过哈希函数算法，将k的哈希值转换成数组的下标。
 *  第四步：拿到下标后，如果数组下标位置上没有链表，就把Node对象添加到这个位置上。  
    如果下标处有链表，此时会拿着Node对象的k和链表中的每一个节点的key，用equals()方法进行比对，如果发现key有相同的，直接用Node对象的v覆盖掉原来旧的value。如果比完了该链表，发现没有key相同的节点，直接存储在该链表的末尾位置。

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

**（2）取出的原理**：调用map.get(k)方法。

*  第一步：先调用k的重写之后hashCode()方法，得出k的哈希值。
 *  第二步：将k的哈希值转换成数组下标，通过下标定位到数组对应的下标位置上。
 *  第三步：如果数组下标位置上什么也没有，直接return null。如果下标位置上有单链表，拿着k和链表中每一个节点的key进行equals()比对，如果找到了有相同的key，返回对应的value。如果找完了该链表都发现没有相同的key，最后return null。

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

4、为什么HashMap存储无序不可重复？

为什么无序：因为你不知道存进去的元素会挂在数组的哪一个链表中。

不可重复是怎么做到的：equals()方法来保证HashMap集合的key不可重复，如果key重复了，value值会覆盖。

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

5、所以说存储到HashMap集合的元素，一定要同时重写hashCode()和equals()方法，并且重写要得当，彻底。

（1）假设重写的hashCode()方法返回一个固定的整数值，思考一下，会导致什么问题？

答：如果重写的hashCode()返回一个固定的值，那么在存储元素的时候，都会定位在数组的固定下标上，存储结构就变成了纯单向链表，将无法发挥出哈希表的性能与效率。

我们把这种情况称为：哈希表散列分布不均匀。

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

（2）那把hashCode()方法的返回值都设定为不一样吗？

答：也不行。因为当hashCode()方法的返回值都不一样时，存储元素的时候，定位到的每个下标都不一样，都会直接存储在数组的下标处，那么这样的话，哈希表就变成了单纯的一维数组，也属于散列分布不均匀，不能发挥出哈希表的性能与效率。

所以说，哈希表对元素重写hashCode()方法特别严格，返回值不能都一样，也不能都不一样。重写hashCode()方法需要一定的技巧。

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

6、那么正确如何重写equals()和hashCode()方法呢？

注意：如果一个类的equals()方法重写了，那么hashCode()方法必须重写。

如果两个对象比较，equals()方法如果返回true，表示两个对象内容相同，那么这两个对象的哈希值也必须是一样的，即hashCode方法的返回值相同。

那么到底怎么重写？  
不需要自己手动去重写，用写代码的工具自动生成。

例如：IDEA中“alt + insert”就可以看到hashCode()和equals()重写的方法。  
这两个方法必须同时生成。

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

7、HashMap集合的默认初始化容量是16，默认加载因子是0.75。

（1）这个默认加载因子当HashMap集合底层数组的容量达到75%的时候，数组开始自动扩容到原容量的2倍。

（2）扩展：当容量达到75%，会调用一个叫reSize()方法，该方法是将旧容量进行位运算<<1，向左移1位，就是乘于2。

（3）如果扩容到很大，源代码中是这样说的，扩容到Integer.MAX\_VALUE（2的32次方）不再扩容。

（4）重点：HashMap集合初始化容量必须是2的幂次方，这是官方建议的。

默认是16，你可以写32，64，128，256等。

这样做可以达到散列分布均匀，为了提高HashMap的存取效率。

参考HashMap的源代码如下：  
// The default initial capacity - MUST be a power of two.  
static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4; // aka 16

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

8、了解一下：jdk8版本之后

*  当HashMap底层数组中每个单向链表的元素超过8之后，底层会把该链表变成红黑树结构。
 *  当红黑树节点小于6之后，会重新变成单向链表结构。

这样做的目的是提高检索效率。

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

9、对于哈希表数据结构来说：

如果两个对象的哈希值相同，一定是放在同一个单向链表中。

当然如果两个对象的哈希值确实不同，但由于哈希算法执行结束之后，转成的下标可能相同，我们把这种情况称为：哈希碰撞。

测试代码：

import java.util.*;
    
    public class Test03 { 
        public static void main(String[] args) { 
            // 创建一个HashSet集合，底层是HashMap
            // 为什么HashSet集合底层会用HashMap集合呢？因为HashSet无序不可重复，而HashMap中的key也是无序不可重复
            // 所以往HashSet中放元素等于往HashSet中的HashMap的key部分放元素，HashMap的value就全是默认值Object类型
            Set<Student> hashSet = new HashSet<>();  // 默认容量是16，达到75%的容量时，会自动扩容到2倍
    
            // 准备两个元素对象
            Student s1 = new Student(1001, "张三");
            Student s2 = new Student(1001, "张三");
    
            // 没有重写equals和hashCode方法之前
            /*hashSet.add(s1); hashSet.add(s2); System.out.println(hashSet.size()); // 2 */
    
            // 重写equals和hashCode方法之后
            hashSet.add(s1);
            hashSet.add(s2);
            System.out.println(hashSet.size());  // 1
    
            // 还有一点，HashMap中允许键值对为<null, null>
            Map map = new HashMap();
            map.put(null, null);
            System.out.println(map.size());  // 1
    
            map.put(null, 100);  // key相同时，会覆盖原来的value值
            System.out.println(map.size());  // 1 说明key为null只能有一个
    
        }
    }
    
    class Student { 
        int id;
        String name;
    
        public Student() { 
        }
    
        public Student(int id, String name) { 
            this.id = id;
            this.name = name;
        }
    
        @Override
        public boolean equals(Object o) { 
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return id == student.id &&
                    Objects.equals(name, student.name);
        }
    
        @Override
        public int hashCode() { 
            return Objects.hash(id, name);
        }
    }

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