在平常的开发当中, HashMap 是 我 https://mp.weixin.qq.com/s/feoOINGSyivBO8Z1gaQVOA 最常用的 Map 类(没有之一), 它支持 null 键和 null 值, 是绝大部分利用键值对存取场景的首选. 需要切记的一点是 --HashMap 不是线程安全的数据结构, 所以不要在多线程场景中应用它.
通常情况下, 我们使用 Map 的主要目的是用来放入 (put), 访问(get) 或者删除(remove), 而对顺序没有特别的要求 --HashMap 在这种情况下就是最好的选择.
01,Hash
对于 HashMap 来说, 难理解的不在于 Map, 而在于 Hash.
Hash, 一般译作 "散列", 也有直接音译为 "哈希" 的, 这玩意什么意思呢? 就是把任意长度的数据通过一种算法映射到固定长度的域上(散列值).
再直观一点, 就是对一串数据 wang 进行杂糅, 输出另外一段固定长度的数据 er-- 作为数据 wang 的特征. 我们通常用一串指纹来映射某一个人, 别小瞧手指头那么大点的指纹, 在你所处的范围内很难找出第二个和你相同的(人的散列算法也好厉害, 有没有?).
对于任意两个不同的数据块, 其散列值相同的可能性极小, 也就是说, 对于一个给定的数据块, 找到和它散列值相同的数据块极为困难. 再者, 对于一个数据块, 哪怕只改动它的一个比特位, 其散列值的改动也会非常的大 -- 这正是 Hash 存在的价值!
在 Java 中, String 字符串的散列值计算方法如下:
- public int hashCode() {
- int h = hash;
- if (h == 0 && value.length> 0) {
- char val[] = value;
- for (int i = 0; i <value.length; i++) {
- h = 31 * h + val[i];
- }
- hash = h;
- }
- return h;
- }
看得懂看不懂都没关系, 我们就当是一个 "乘加迭代运算" 的算法. 借此机会, 我们来看一下 "沉","默","王","二" 四个字符串的散列值是多少.
- String[] cmower = { "沉", "默", "王", "二" };
- for (String s : cmower) {
- System.out.println(s.hashCode());
- }
输出的结果如下(5 位数字):
沉的散列值: 27785 默的散列值: 40664 王的散列值: 29579 二的散列值: 20108
对于 HashMap 来说, Hash(key, 键位)存在的目的是为了加速键值对的查找(你想, 如果电话薄不是按照人名的首字母排列的话, 找一个人该多困难「我的微信好友有不少在昵称前加了 A, 好狠」). 通常情况下, 我们习惯使用 String 字符串来作为 Map 的键, 请看以下代码:
- Map<String, String> map = new HashMap<>();
- String[] cmower = { "沉", "默", "王", "二" };
- for (String s : cmower) {
- map.put(s, s + "月入 25 万");
- }
那 HashMap 会真的会将 String 字符串作为实际的键吗? 我们来看 HashMap 的 put 方法源码:
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
虽然只有一个 putVal()方法的调用, 但是你应该已经发现, HashMap 内部会把 key 进行一个 hash 运算, 具体代码如下:
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
假如 key 是 String 字符串的话, hash()会先获取字符串的 hashCode(散列值), 再对散列值进行位于运算, 最终的值为 HashMap 实际的键(int 值).
既然 HashMap 在 put 的时候使用键的散列值作为实际的键, 那么在根据键获取值的时候, 自然也要先对 get(key)方法的 key 进行 hash 运算, 请看以下代码:
- public V get(Object key) {
- Node<K,V> e;
- return (e = getNode(hash(key), key)) == null ? null : e.value;
- }
02, 散列值冲突怎么解决
尽管散列值很难重复, 我们还是要明白, 这种转换是一种压缩映射, 也就是, 散列值的空间通常远小于输入的空间, 不同的输入可能会散列成相同的输出.
也就是说, key1 ≠ key2, 但 function(key1)有可能等于 function(key2)-- 散列值冲突了. 怎么办?
最容易想到的解决办法就是: 当关键字 key2 的散列值 value 与 key1 的散列值 value 出现冲突时, 以 value 为基础, 产生另一个散列值 value1, 如果 value1 与 value 不再冲突, 则将 value1 作为 key2 的散列值.
依照这个办法, 总会找到不冲突的那个.
03, 初始容量和负载因子
HashMap 的构造方法主要有三种:
- public HashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);
- }
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- }
其中 initialCapacity 为初始容量(默认为 1 << 4 = 16),loadFactor 为负载因子(默认为 0.75). 初始容量是 HashMap 在创建时的容量(HashMap 中桶的数量); 负载因子是 HashMap 在其容量自动增加之前可以达到多满的一种尺度.
当 HashMap 中的条目数超出了负载因子与当前容量的乘积时, 则要对 HashMap 扩容, 增加大约两倍的桶数.
通常, 默认的负载因子 (0.75) 是时间和空间成本上的一种折衷. 负载因子过高虽然减少了空间开销, 但同时增加了查询成本. 如果负载因子过小, 则初始容量要增大, 否则会导致频繁的扩容.
在设置初始容量时应该考虑到映射中所需的条目数及其加载因子, 以便最大限度地减少扩容的操作次数.
如果能够提前预知要存取的键值对数量的话, 可以考虑设置合适的初始容量(大于 "预估元素数量 / 负载因子", 并且是 2 的幂数).
04, 小结
在之前很长的一段时间内, 我对 HashMap 的认知仅限于会用它的 put(key, value)和 value = get(key).
但, 当我强迫自己每周要输出一篇 Java 方面的技术文章后, 我对 HashMap 真的 "深入浅出" 了 -- 散列值(哈希值), 散列冲突(哈希冲突), 初始容量和负载因子, 竟然能站在我面前一直笑 -- 而原先, 我见到这些关键字就逃之夭夭了, 我怕见到它们.
PS: 欢迎我的公众号「沉默王二」, 一个不止写代码的程序员, 还写有趣有益的文字, 给不喜欢严肃的你.
来源: https://juejin.im/post/5c8f39586fb9a070d20f1384