java map 面试题_Java 面试系列：集合详解之 Map + 面试题

集合有两个大接口：Collection 和 Map，本文重点来讲解集合中另一个常用的集合类型 Map。

以下是 Map 的继承关系图：

avatar

Map 简介

Map 常用的实现类如下：

Hashtable：Java 早期提供的一个哈希表实现，它是线程安全的，不支持 null 键和值，因为它的性能不如 ConcurrentHashMap，所以很少被推荐使用。

HashMap：最常用的哈希表实现，如果程序中没有多线程的需求，HashMap 是一个很好的选择，支持 null 键和值，如果在多线程中可用 ConcurrentHashMap 替代。

TreeMap：基于红黑树的一种提供顺序访问的 Map，自身实现了 key 的自然排序，也可以指定 Comparator 来自定义排序。

LinkedHashMap：HashMap 的一个子类，保存了记录的插入顺序，可在遍历时保持与插入一样的顺序。

Map 常用方法

常用方法包括：put、remove、get、size 等，所有方法如下图：

enter image description here

使用示例，请参考以下代码：

Map hashMap = new HashMap();

// 增加元素

hashMap.put("name", "老王");

hashMap.put("age", "30");

hashMap.put("sex", "你猜");

// 删除元素

hashMap.remove("age");

// 查找单个元素

System.out.println(hashMap.get("age"));

// 循环所有的 key

for (Object k : hashMap.keySet()) {

System.out.println(k);

}

// 循环所有的值

for (Object v : hashMap.values()) {

System.out.println(v);

}

以上为 HashMap 的使用示例，其他类的使用也是类似。

HashMap 数据结构

HashMap 底层的数据是数组被成为哈希桶，每个桶存放的是链表，链表中的每个节点，就是 HashMap 中的每个元素。在 JDK 8 当链表长度大于等于 8 时，就会转成红黑树的数据结构，以提升查询和插入的效率。

HashMap 数据结构，如下图：

enter image description here

HashMap 重要方法

1)添加方法：put(Object key, Object value)

执行流程如下：

对 key 进行 hash 操作，计算存储 index；

判断是否有哈希碰撞，如果没碰撞直接放到哈希桶里，如果有碰撞则以链表的形式存储；

判断已有元素的类型，决定是追加树还是追加链表，当链表大于等于 8 时，把链表转换成红黑树；

如果节点已经存在就替换旧值；

判断是否超过阀值，如果超过就要扩容。

源码及说明：

public V put(K key, V value) {

// 对 key 进行 hash()

return putVal(hash(key), key, value, false, true);

}

static final int hash(Object key) {

int h;

// 对 key 进行 hash() 的具体实现

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node[] tab; Node p; int n, i;

// tab为空则创建

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

// 计算 index，并对 null 做处理

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node e; K k;

// 节点存在

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

// 该链为树

else if (p instanceof TreeNode)

e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

// 该链为链表

else {

for (int binCount = 0; ; ++binCount) {

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

}

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

}

// 写入

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

// 超过load factor*current capacity，resize

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

put() 执行流程图如下：

enter image description here