当我写下Map<String,Object> map = new HashMap<>();我到底在写什么？
- 我什么时候会写HashMap?
- 一个函数同时需要返回 多种 状态的情况
- 举例：一个列表有100个数据，一个函数对该列表进行处理，并将该列表的数据划分为A,B,C 3部分，此时函数的返回值就适用用map
- 当需要保存键值对时
- 一个函数同时需要返回 多种 状态的情况
- HashMap的实现是什么？
- 数组 + linkedList + 红黑树
- 容量阈值 都是指的HashMap中实际存放数据的数组的容量阈值
- 我该怎么写HashMap?
// 1. 新建一个HashMap对象
Map<String,Object> map = new HashMap<>();
// 2. 向map中添加数据
map.put("key", value);
// 3. 从map中删除数据
map.remove("key"); or map.remove("key", value);
// 4.修改map中的数据
map.replace("key", value); or map.replace("key", value, value); or map.put("key", value);
// 5. 从map中查找数据
map.get("key");
// 6. map的数据如何遍历
String key : map.keySet() // 遍历键
Object boj : map.values() // 遍历值
Map.Entry<String, Object> entry : map.entrySet() // 遍历键值对
- 当新建一个HashMap对象时 到底发生了什么？
- 从下方HashMap的构造函数可以看出:只是给出了初始容量-16 和加载因子-0.75。
- 从名字就看的出来 这两个初始值 是决定 什么时候进行hashmap 自动扩容的，但 此时内部实现的数组并没有初始化，并没有实际用到这两个值（毕竟构造函数没有相关代码）。
- 这两个值 实际使用是在 执行扩容的resize()方法中，且只有向HashMap中添加数据时才会扩容，可以理解为 这里的两个参数是在 第一次调用put才用到。使用时，两者相乘的结果转为int类型 作为阈值。
- 顺便说一下，扩容时，还会重新决定各个键值对在HashMap的实现数组中的索引（e.hash & （容量 - 1））。如果数组中存储的是链接表 or 红黑树，新的索引由（e.hash & 容量） == 0 比较决定。这个很容易理解，就是看容量左边那一位是不是0，若是则索引不变，若不是则新索引 = 旧索引+ 容量。这三种情况索引膨胀后 索引不会碰撞，这得益于按2的指数增长容量的方式
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 向map中添加数据 又发生了什么？
哈希码部分参考：https://www.zhihu.com/question/20733617
- 扰动函数-hash： 混合 hashcode的高位和低位，加大哈希码低位的随机性。将高位和低位的特征都汇集到低位。且由上一个问题的理解里可知哈希码最终还决定了具体存放在数组的那个位置，所以这么做，在数组容量较小的情况下，只会用到低位来决定放置位置，低位具备了更多的特征，也会减少碰撞
- 扩容-每次扩容1倍；扩容时，需重新分配索引
- 对新增对象 判断放置索引，若该索引处无对象，则放置
- 若该索引处已经有对象，且已有对象与新增对象 hash一致,键一致，
- 若已有对象是红黑树， 则加入树
- 其他情况则已有对象是 链表，新对象加入链表
- 若新对象加入链表后，链表长度 超过链表阈值，则将链表转为红黑树
- 4，5，6中 若 键值重复【 hash一致,键一致】，则替换值， 并返回旧值
- 修改后，数组大小超过 阈值，扩容
- 关于红黑树，见https://www.cnblogs.com/liwei2222/p/8013367.html
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> 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<K,V>)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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 增删改查就不一一说了，原理都类似于put方法
小礼物走一走，来简书关注我
作者：shaYanL
链接：https://www.jianshu.com/p/6b2e350e99be
来源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。