HashMap 里面涉及了很多的知识点, 可以比较全面考察面试者的基本功, 想要拿到一个好 offer, 这是一个迈不过的坎, 接下来我用最通俗易懂的语言带着大家揭开 HashMap 的神秘面纱.
一: HashMap 的节点
HashMap 是一个集合, 键值对的集合, 源码中每个节点用 Node<K,V > 表示
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- ...
- }
Node 是一个内部类, 这里的 key 为键, value 为值, next 指向下一个元素, 可以看出 HashMap 中的元素不是一个单纯的键值对, 还包含下一个元素的引用.
二: HashMap 的数据结构
HashMap 的数据结构为 数组 +(链表或红黑树), 上图:
为什么采用这种结构来存储元素呢?
数组的特点: 查询效率高, 插入, 删除效率低.
链表的特点: 查询效率低, 插入删除效率高.
在 HashMap 底层使用数组加 (链表或红黑树) 的结构完美的解决了数组和链表的问题, 使得查询和插入, 删除的效率都很高.
三: HashMap 存储元素的过程
有这样一段代码:
- HashMap<String,String> map = new HashMap<String,String>();
- map.put("刘德华","张惠妹");
- map.put("张学友","大 S");
现在我要把键值对 "刘德华","张惠妹" 存入 map:
第一步: 计算出键 "刘德华" 的 hashcode, 该值用来定位要将这个元素存放到数组中的什么位置.
什么是 hashcode? 在 Object 类中有一个方法:
public native int hashCode();
该方法用 native 修饰, 所以是一个本地方法, 所谓本地方法就是非 java 代码, 这个代码通常用 c 或 c++ 写成, 在 java 中可以去调用它. 调用这个方法会生成一个 int 型的整数, 我们叫它哈希码, 哈希码和调用它的对象地址和内容有关.
哈希码的特点是:
对于同一个对象如果没有被修改 (使用 equals 比较返回 true) 那么无论何时它的 hashcode 值都是相同的.
对于两个对象如果他们的 equals 返回 false, 那么他们的 hashcode 值也有可能相等.
明白了 hashcode 我们再来看元素如何通过 hashcode 定位到要存储在数组的哪里, 通过 hashcode 值和数组长度取模我们可以得到元素存储的下标. 刘德华的 hashcode 为 20977295 数组长度为 16 则要存储在数组索引为 20977295%16=1 的地方.
可以分两种情况:
1. 数组索引为 1 的地方是空的, 这种情况很简单, 直接将元素放进去就好了.
2. 已经有元素占据了索引为 1 的位置, 这种情况下我们需要判断一下该位置的元素和当前元素是否相等, 使用 equals 来比较.
如果使用默认的规则是比较两个对象的地址. 也就是两者需要是同一个对象才相等, 当然我们也可以重写 equals 方法来实现我们自己的比较规则最常见的是通过比较属性值来判断是否相等.
如果两者相等则直接覆盖, 如果不等则在原元素下面使用链表的结构存储该元素.
每个元素节点都有一个 next 属性指向下一个节点, 这里由数组结构变成了数组 + 链表结构, 红黑树又是怎么回事呢?
因为链表中元素太多的时候会影响查找效率, 所以当链表的元素个数达到 8 的时候使用链表存储就转变成了使用红黑树存储, 原因就是红黑树是平衡二叉树, 在查找性能方面比链表要高.
四: HashMap 中的两个重要的参数
HashMap 中有两个重要的参数: 初始容量大小和加载因子, 初始容量大小是创建时给数组分配的容量大小, 默认值为 16, 用数组容量大小乘以加载因子得到一个值, 一旦数组中存储的元素个数超过该值就会调用 rehash 方法将数组容量增加到原来的两倍, 专业术语叫做扩容. 在做扩容的时候会生成一个新的数组, 原来的所有数据需要重新计算哈希码值重新分配到新的数组, 所以扩容的操作非常消耗性能.
创建 HashMap 时我们可以通过合理的设置初始容量大小来达到尽量少的扩容的目的. 加载因子也可以设置, 但是除非特殊情况不建议设置.
来源: http://www.bubuko.com/infodetail-3356295.html