HashMap？面试？我是谁？我在哪

发表于 | 阅读次数:
字数统计: 459 | 阅读时长 ≈ 1

面试经常被问到做个笔记，emmmmm

为什么用HashMap？

  • HashMap 是一个散列桶（数组和链表），它存储的内容是键值对 key-value 映射
  • HashMap 采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
  • HashMap 是非 synchronized，所以 HashMap 很快
  • HashMap 可以接受 null 键和值，而 Hashtable 则不能（原因就是 equlas() 方法需要对象，因为 HashMap 是后出的 API 经过处理才可以）

HashMap 的工作原理是什么？

HashMap 是基于 hashing 的原理

我们使用 put(key, value) 存储对象到 HashMap 中，使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时，我们先对键调用 hashCode() 方法，计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。

这里关键点在于指出，HashMap 是在 bucket 中储存键对象和值对象，作为Map.Node。

以下是 HashMap 初始化
简化的模拟数据结构：

1
2
3
4
5
6
7
Node[] table = new Node[16]; // 散列桶初始化，table
class Node {
    hash; //hash值
    key; //键
    value; //值
    node next; //用于指向链表的下一层（产生冲突，用拉链法）
}

以下是具体的 put 过程（JDK1.8）

  1. 对 Key 求 Hash 值，然后再计算下标
  2. 如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的 Hash 值相同，需要放到同一个 bucket 中）
  3. 如果碰撞了，以链表的方式链接到后面
  4. 如果链表长度超过阀值（TREEIFY THRESHOLD==8），就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
  5. 如果节点已经存在就替换旧值
  6. 如果桶满了（容量16*加载因子0.75），就需要 resize（扩容2倍后重排）