HashMap 底层原理在 JDK 1.7 中HashMap 中保存的是 Entry 对象key 和 value 都是 Entry 对象的属性。HashMap 在 JDK 1.7 中底层数据结构是数组链表JDK 1.8 中是数组链表红黑树。HashMap 在使用 put 方法添加元素时会根据要添加元素的 key 的 hashCode 方法计算 hash 值然后根据 hash 值计算出元素在数组中的存储位置。当数组当前位置已经存在元素时如果两个元素 key 计算出的 hash 值不相同则说明是两个不同的元素把数组当前位置上原有的元素取出然后把新的元素添加到数组当前位置上新的元素的 next 属性指向原来的元素形成链表结构HashMap 中的元素都是 Entry 对象Entry 对象有 next 属性用于记录下一个元素的位置。当数组当前位置已经存在元素时如果两个元素 key 计算出的 hash 值相同equals 方法比较返回 true说明是两个相同的元素则把旧元素从数组位置上取出新的元素放到数组位置上put 会返回被替换元素的 value 值。如果数组当前位置没有元素则直接添加元素到数组当前位置put 方法返回 null。HashMap 默认的数组大小是 16计算因子是 0.75,16 * 0.75 12当数组的长度达到临界值 12 时会触发数组的扩容机制。JDK 1.7 和 JDK 1.8 HashMap 的不同之处JDK 1.7 中创建 HashMap 对象时就初始化了数组的长度。JDK 1.8 中创建 HashMap 对象时数组长度是 0首次添加元素初始化数组长度。JDK 1.7 中 HashMap 中保存的是 Entry 对象key 和 value 都是 Entry 对象的属性。JDK 1.8 中 HashMap 中保存的是 Node 对象key 和 value 都是 Node 对象的属性。JDK 1.7 中添加元素时当数组位置上已经存在元素时使用头插法添加元素即新添加的元素指向原来的元素。JDK 1.8 中使用尾插法添加元素即原来的元素指向新添加的元素。JDK 1.7 中底层数据结构是数组链表JDK 1.8 中是数组链表红黑树。当数组某个索引位置上的元素个数达到 8 时并且数组长度达到 64 时这个索引位置的元素由链表转为红黑树可以提高查询修改删除操作的效率。当使用红黑树的索引位置上的元素数量低于 6 时退化为链表结构因为红黑色占用的空间大。面试时直接回答 JDK 1.8 的 HashMap 原理即可JDK 1.8 中 HashMap 中保存的是 Node 对象key 和 value 都是 Node 对象的属性。JDK 1.8 中底层数据结构是数组链表红黑树。当数组某个索引位置上的元素个数达到 8 时并且数组长度达到 64 时这个索引位置的元素由链表转为红黑树可以提高查询修改删除操作的效率。当使用红黑树的索引位置上的元素数量低于 6 时退化为链表结构因为红黑色占用的空间大。HashMap 在使用 put 方法添加元素时会根据要添加元素的 key 的 hashCode 方法计算 hash 值然后根据 hash 值计算出元素在数组中的存储位置。当数组当前位置已经存在元素时如果两个元素 key 计算出的 hash 值不相同则说明是两个不同的元素旧的元素的 next 属性会指向新的元素形成链表结构HashMap 中的元素都是 Node 对象Node 对象有 next 属性用于记录下一个元素的位置。当数组当前位置已经存在元素时如果两个元素 key 计算出的 hash 值相同equals 方法比较返回 true说明是两个相同的元素则把旧元素从数组位置上取出新的元素放到数组位置上put 会返回被替换元素的 value 值。如果数组当前位置没有元素则直接添加元素到数组当前位置put 方法返回 null。HashMap 默认的数组大小是 16计算因子是 0.75,16 * 0.75 12当数组的长度达到临界值 12 时会触发数组的扩容机制。
