public class TestHashMap { /** * HashMap是数组和链表组合构成的数据结构 * 数组里面每个地方都存了key-value这样的实例Java7叫Entry，Java8叫Node * 因为本身所有的位置都为null，在put插入的时候会根据key的hash去计算一个index值。 * 为什么需要链表？ * 我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是"12"和"21"我们都去hash有一定的概率会一样，如下面情况"12"和"21"hash到一个值上，那就形成了链表。 * * 数组容量是有限的，数据多次插入，到达一定的数量就会进行扩容，也就是resize * 扩容条件：Capacity：HashMap当前长度；LoadFactor：负载因子，默认值0.75f * 扩容分2步：1、扩容：创建一个Entry的空数组，长度是原数组的2倍 2、ReHash:遍历原Entry数组，把所有的Entry重新Hash到新数组 * * 为什么要重新Hash,直接复制过去不好吗？ * 因为长度扩大以后，Hash的规则也随之改变 * Hash的公式---> index = HashCode（Key） & （Length - 1） * 原来长度（Length）是8你位运算出来的值是4 ，新的长度是16你位运算出来的值明显不一样了。 * * 新的Entry节点，插入链表的时候，Java8之前是头插法，Java8之后是尾部插法 * 使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。 * Java7在多线程操作HashMap时可能引起死循环（Infinite Loop），原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。 * Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。 * * java8之后链表有红黑树的部分，大家可以看到代码已经多了很多if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。 * * HashMap的默认初始化长度 DEFAULT_INITIAL_CAPACITY = 16; DEFAULT_LOAD_FACTOR = 0.75f; * 在创建HashMap的时候，阿里巴巴规范插件会提醒我们最好赋初值，而且最好是2的幂, * 这样是为了位运算的方便，位与运算比算数计算的效率高了很多(效果与取模一样)，之所以选择16，是为了服务将Key映射到index的算法。 * 因为在使用2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值，只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的（实现均匀分布） * * 为什么我们重写equals方法的时候需要重写hashCode方法呢？ * HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”AB“和”BA“的index可能是一样的，在一个链表上的 * 所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值 * 不然一个链表的对象，你哪里知道你要找的是哪个，到时候发现hashCode都一样，区分不了。 */ public static void main(String[] args) { //集合初始化时，指定集合初始值大小 HashMap map = new HashMap<>(16); map.put("12", "AB"); map.put("21", "AB"); map.put("11", "AB"); map.put("10", "AB"); int index1 = map.get("12").hashCode(); int index2 = map.get("21").hashCode(); int index3 = map.get("11").hashCode(); int index4 = map.get("10").hashCode(); System.out.println(map.size());//4 System.out.println(index1);//2081 System.out.println(index2);//2081 System.out.println(index3);//2081 System.out.println(index4);//2081 Object o1 = map.get("12"); Object o2 = map.get("21"); Object o3 = map.get("11"); Object o4 = map.get("10"); System.out.println(o1.equals(o2));//true System.out.println(o3.equals(o4));//true } }