03-Map
Map（key）底层哈希表（数组+链表），必须重写hashCode(), equals()
- Hashtable
- JDK1.0，效率低，线程安全
- key不可存null
- HashMap
- JDK1.2，效率高，线程不安全
- key可存null且唯一
- LinkedHashMap
- 有序（增加双向链表），输入顺序
- TreeMap => 底层二叉树
- 有序（Comparator顺序）
1. API
public class T1_Map {
/*
* 1. 增加：put(K key, V value)
* 2. 删除：clear(), remove(Object key)
* 3. 修改：
* 4. 查看：get(Object key), entrySet(), keySet(), values(), size()
* 5. 判断：containsKey(Object key), containsValue(Object value), equals(Object o), isEmpty()
*/
@Test
public void API() {
Map<String, Integer> map = new HashMap<>();
System.out.println("map.put(a, 1111) = " + map.put("a", 1111));
map.put("b", 2222);
map.put("c", 3333);
// 进行覆盖。返回被覆盖value
System.out.println("map.put(a, 4444) = " + map.put("a", 4444));
map.put("d", 5555);
map.put("e", 6666);
// 清空
map.clear();
// 移除
map.remove("b");
System.out.println("map.size() = " + map.size()); // 无序、唯一
System.out.println(map);
System.out.println("map.containsKey(c) = " + map.containsKey("c"));
System.out.println("map.containsValue(3333) = " + map.containsValue(3333));
System.out.println("-----------------------------------");
Map<String, Integer> map2 = new HashMap<>();
map2.put("a", 1111);
map2.put("b", 2222);
map2.put("c", 3333);
map2.put("a", 4444);
map2.put("d", 5555);
map2.put("e", 6666);
System.out.println("map == map2 => " + (map == map2));
// equals进行了重写，比较的是集合中的值是否一致
System.out.println("map.equals(map2) = " + map.equals(map2));
System.out.println("map.isEmpty() = " + map.isEmpty());
System.out.println("map.get(d) = " + map.get("d"));
System.out.println("----------------- keySet() ------------------");
// keySet()
Set<String> set = map.keySet();
for (String key : set) {
System.out.println(key + " => " + map.get(key));
}
System.out.println("------------------ values() -----------------");
// values()
Collection<Integer> values = map.values();
for (Integer val : values) {
System.out.println(val);
}
System.out.println("----------------- entrySet() ------------------");
// entrySet()
Set<Map.Entry<String, Integer>> entries = map.entrySet();
for (Map.Entry<String, Integer> e : entries) {
System.out.println(e.getKey() + " => " + e.getValue());
}
}
/**
* 唯一、有序（输入顺序）
*/
@Test
public void LinkedHashMap() {
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("b", 2222);
map.put("a", 1111);
// 返回覆盖value
System.out.println("map.put(a, 4444) = " + map.put("a", 4444));
map.put("d", 5555);
map.put("c", 3333);
map.put("e", 6666);
System.out.println("map.size() = " + map.size());
System.out.println(map);
}
/**
* 唯一、有序（升序、降序）
*/
@Test
public void TreeMap() {
// key为String类型
TreeMap<String, Integer> map = new TreeMap<>();
map.put("b", 2222);
map.put("a", 1111);
map.put("a", 4444); // 返回覆盖value
map.put("d", 5555);
map.put("c", 3333);
map.put("e", 6666);
System.out.println("map.size() = " + map.size());
System.out.println(map);
System.out.println("----------------- inner_comparator ------------------");
// key为引用类型
@Getter
@ToString
@AllArgsConstructor
class Student implements Comparable<Student> {
private final int age;
private final double height;
@Override
public int compareTo(Student o) {
return this.getAge() - o.getAge();
}
}
// inner_comparator
Map<Student, Integer> map_ref = new TreeMap<>();
map_ref.put(new Student(4, 130), 1001);
map_ref.put(new Student(3, 120), 1003);
// compare相等的key，返回被覆盖node的value
System.out.println("Student(4, 150), 1023) = " + map_ref.put(new Student(4, 150), 1023));
map_ref.put(new Student(2, 110), 1671);
map_ref.put(new Student(1, 140), 1891);
map_ref.put(new Student(5, 140), 1892);
System.out.println("map_ref.size() = " + map_ref.size());
System.out.println(map_ref);
System.out.println("----------------- outer_comparator ------------------");
// outer_comparator
Map<Student, Integer> map_outer = new TreeMap<>(Comparator.comparing(Student::getHeight));
map_outer.put(new Student(4, 130), 1001);
map_outer.put(new Student(3, 120), 1003);
map_outer.put(new Student(4, 150), 1023);
map_outer.put(new Student(2, 110), 1671);
map_outer.put(new Student(1, 140), 1891);
map_outer.put(new Student(5, 140), 1892);
System.out.println("map_outer.size() = " + map_outer.size());
System.out.println(map_outer);
}
}
2. HashMap
1. HashTable
- HashTable
- JDK1.0。线程安全，效率低。key不可为null
- HashMap
- JDK1.2。线程不安全，效率高。key可为null，且唯一
2. SC
- HashMap底层什么实现的？
- 底层数组的默认长度是多少，长度要求？加载因子？扩容策略？
- 策略2倍，扩容算法JDK8更先进
- 数组元素的类型？类型中的属性？
- 为什么重写
hashCode()，equals()？ - 链表是单向、双向？新增node头插、尾插？（7上8下）
- 链表 => 红黑树策略？
链表 >= 8，数组 >= 64=> 链表树化（红黑树）
- JDK
- 初始化。JDK8懒汉式，JDK7饿汉式
put()7上8下。7链表不树化- 扩容数据转移。JDK7全部重新
hashCode()，JDK8更先进
public class T2_HashMap8 {
@Test
public void T2_SC() {
// 1. 无参构造
HashMap<String, Integer> map = new HashMap<>();
// 2. 有参构造
HashMap<Integer, String> mapArgs = new HashMap<>(10);
/*
* 3. put()
* 1. hash不同
* 2. hash相同，key相同
* 3. hash相同，key不同
*/
map.put("通话", 10);
map.put("随便", 20);
map.put("通话", 30); // hash、key相同。返回value
map.put("重地", 40); // hash相同，key不同
// 不同的key，相同的hash
System.out.println("通话.hashCode() = " + "通话".hashCode());
System.out.println("重地.hashCode() = " + "重地".hashCode());
System.out.println("Integer.hashCode() = " + Integer.hashCode(11));
}
}
1. %运算
%本质为a的二进制的最后n位
// 按位运算
@Test
public void T1_bitwise() {
int x = 15;
/*
1. a % b == a & (b - 1); => b为2^n
2. 2^n => 100...000，1后面n个0
3. 2^n - 1 => 011...111，0后面n个1
4. % 本质为a的二进制的最后n位
*/
int a = x % 2 ^ 3;
int b = x & (2 ^ 3 - 1); // 0111，只保留x二进制后三位
int c = x / 2 ^ 3; // x >> n，移除x二进制后三位
}
2. loadFactor
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
- 加载因子（装填因子）：表示hash表中元素的填满程度
- 太大，hash碰撞大（链表多，查询慢），空间利用高（空间好、时间不好）
- 太小，hash碰撞小（链表少，查询快），空间利用低（时间好，空间不好）
- 0.75是统计值、经验值，时间、空间折中
- 哈希表数组_默认长度16
- 加载因子（装填因子）0.75f
- 数组长度要求。(>= cap)且最小
2^n - 数组扩容2倍
- 新node尾插上链
- 链表树化 =>
(桶 >= 8) && (数组.length >= 64)
3. JDK8
// 多余。但是设计者觉得没有必要删除
// AbstractMap<K,V> implements Map<K,V>
class _HashMap8<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
// 1. 哈希表数组_默认长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 哈希表数组_最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
/*
* 2. 加载因子（装填因子），表示hash表中元素的填满程度
* 太大容易引起hash冲突，太小容易浪费。0.75经过大量运算后得到的最优值
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
float loadFactor;
int threshold; // 数组扩容阈值
// 数组，元素为Entry类型
transient Node<K, V>[] table;
transient int size;
transient int modCount;
static final int MIN_TREEIFY_CAPACITY = 64; // min_treeify_capacity
static final int TREEIFY_THRESHOLD = 8; // treeify_threshold
// 3.1. noArgsCtor。new HashMap<>();
public _HashMap8() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75f
}
// 3.2. argsCtor。new HashMap<>(10);
public _HashMap8(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 3.3. (10, 0.75)
public _HashMap8(int initialCapacity, float loadFactor) {
// 健壮性处理
this.loadFactor = loadFactor; // 0.75
this.threshold = tableSizeFor(initialCapacity); // 16
}
// 4. 数组长度要求。(>= cap)且最小`2^n`
static int tableSizeFor(int cap) { // 10
int n = cap - 1;
// 无符号右移，最高位后全变为1
// 如n = 9，1001 => 1111 => (+ 1 = 10000) => (2^4 = 16)
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // 16
}
// 5. put();
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// hash值
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 1. table == null
* 2. hash无碰撞
* 3. hash碰撞，key相同
* 4. hash碰撞，key不同
*/
V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
// 1. noArgsCtor
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // Node[16]
// 2.1. hash无碰撞
if ((p = tab[i = (n - 1) & hash]) == null) // (n - 1) & hash => (2^n - 1) & hash => index
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e;
K k;
// 2.2.1. hash碰撞，key相同
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// key为String，|| 后的equals()不需要进行，提交效率
e = p;
// else if (p instanceof TreeNode)
// e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 2.3. hash碰撞，key不同
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // 新node尾插上链
// 4. >= (8 - 1) 链表树化
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 2.2.2. key相同
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
// 下一个
p = e;
}
}
// 2.2.3. hash碰撞，key相同
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; // 覆盖value
// afterNodeAccess(e);
return oldValue; // 返回value旧值
}
}
++modCount;
// 3. 长度 > 阈值，进行扩容
if (++size > threshold)
resize();
// afterNodeInsertion(evict);
return null;
}
/**
* 数组扩容
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 已有容量
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 数组扩容2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值扩容2倍
newThr = oldThr << 1;
}
// argsCtor
else if (oldThr > 0) {
newCap = oldThr; // 2^n
}
// noArgsCtor
else {
newCap = DEFAULT_INITIAL_CAPACITY; // 16
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 = 12
}
// argsCtor
if (newThr == 0) {
float ft = (float) newCap * loadFactor; // 2^n * 0.75
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 新底层数组
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
// oldTable[] => newTable[]
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 无链node
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
/*
* 链表node => 新数组
* -----------------------------------
* 1. % 本质为a的二进制的最后n位
* 2. 数组扩容为2倍，即key的hash多保留一位
* 3. 多保留的一位，值为0在newTab[j]，为1在newTab[j + oldCap]
*/
else {
Node<K, V> loHead = null, loTail = null; // lo => low
Node<K, V> hiHead = null, hiTail = null; // hi => high
Node<K, V> next;
do {
next = e.next;
// oldTab[j] => newTab[j]
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// oldTab[j] => newTab[j + oldCap]
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
/*
* 链表树化 => (桶 >= 8) && (数组.length >= 64)
*/
final void treeifyBin(Node<K, V>[] tab, int hash) {
int n, index;
Node<K, V> e;
// 16 < 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize(); // 数组扩容，不树化
}
// 单向链表 => 双向链表
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K, V> hd = null, tl = null; // head == tail == null
do {
// Node => TreeNode
TreeNode<K, V> p = replacementTreeNode(e, null);
if (tl == null) // 确定真实root
hd = p;
else { // 维护双向性
p.prev = tl;
tl.next = p;
}
// 切换移动root
tl = p;
} while ((e = e.next) != null);
// 双向链表 => 红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
static class Node<K, V> {
int hash;
K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
// class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
// class Entry<K,V> extends HashMap.Node<K,V>
// extends Node<K, V> 对SC修改
static class TreeNode<K, V> extends Node<K, V> {
TreeNode<K, V> parent;
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev;
boolean red;
TreeNode(int hash, K key, V val, Node<K, V> next) {
super(hash, key, val, next);
}
/**
* 双向链表 => 红黑树
*/
final void treeify(Node<K, V>[] tab) {
}
final void split(_HashMap8<K, V> map, Node<K, V>[] tab, int index, int bit) {
}
}
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
return new Node<>(hash, key, value, next);
}
@Override
public Set<Entry<K, V>> entrySet() {
return null;
}
}
4. JDK7
- 和JDK8区别
- 链表头插
- oldTable[] => newTable[] 算法不够先进
- 无红黑树
public class T3_HashMap7 {
@Test
public void SC() {
// 1. 无参构造
// JDK1.7支持<>内容可以不写
HashMap<String, Integer> map = new HashMap<>();
// 2. 有参构造
HashMap<Integer, String> mapArgs = new HashMap<>(10);
/*
* 3. put()
* 1. hash不同
* 2. hash相同，key相同
* 3. hash相同，key不同
*/
map.put("通话", 10);
map.put("随便", 20);
map.put("通话", 30); // hash、key相同
map.put("重地", 40); // hash相同，key不同
// 不同的key，相同的hash
System.out.println("通话.hashCode() = " + "通话".hashCode());
System.out.println("重地.hashCode() = " + "重地".hashCode());
System.out.println("Integer.hashCode() = " + Integer.hashCode(11));
}
}
// 多余。但是设计者觉得没有必要删除
// AbstractMap<K,V> implements Map<K,V>
class _HashMap7<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
// 1. 哈希表数组_默认长度16
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 哈希表数组_最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
/*
* 2. 加载因子（装填因子），表示hash表中元素的填满的程度
* 太大容易引起hash冲突，太小容易浪费。0.75经过大量运算后得到的最优值
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
int threshold; // 数组扩容阈值
// 数组，元素为Entry类型
transient Entry<K, V>[] table;
transient int size;
transient int modCount;
// 3.1. noArgsCtor。new HashMap<>();
public _HashMap7() { // (16, 0.75f)
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 3.2. argsCtor。new HashMap<>(10);
// 有参构造器。自定义初始化容量、加载因子
public _HashMap7(int initialCapacity, float loadFactor) {
// 4. 数组长度。(>= cap)的最小2^n
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
// 装填因子
this.loadFactor = loadFactor;
// 扩容阈值（16 * 0.75 = 12）
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
}
// 5. put(); 1. hash相同 2. hash碰撞，key相同 3. hash碰撞，key不同
public V put(K key, V value) {
// 允许key为null，HashTable不允许
if (key == null)
return putForNullKey(value);
// key哈希值
int hash = hash(key);
// index
int i = indexFor(hash, table.length);
// 5.1. hash碰撞，key相同（遍历整条链表）
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
// 覆盖value旧值，不替换key
e.value = value;
e.recordAccess(this);
return oldValue; // 返回value旧值
}
}
modCount++;
// 5.2. hash不同
// 5.3. hash碰撞，key不同
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 6. 数组扩容 (容量 >= 阈值 && table[index]不为空)
if ((size >= threshold) && (null != table[bucketIndex])) {
// 6.1. 扩容2倍
resize(2 * table.length);
// 重新hash
hash = (null != key) ? hash(key) : 0;
// 重新index
bucketIndex = indexFor(hash, table.length);
}
// 7. 链表头插
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex];
// 头插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
// 数组扩容（2倍）
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
Entry[] newTable = new Entry[newCapacity];
// boolean oldAltHashing = useAltHashing;
// useAltHashing |= sun.misc.VM.isBooted() &&
// (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// boolean rehash = oldAltHashing ^ useAltHashing;
boolean rehash = true; // 假值，防止报错
// 6.3. oldTable[] => newTable[]
transfer(newTable, rehash);
// 新数组切换
table = newTable;
// 更新阈值
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// oldTable[] => newTable[]
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K, V> e : table) {
while (null != e) {
Entry<K, V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// newIndex
int i = indexFor(e.hash, newCapacity);
// 6.4. 头插法（画图理解）
e.next = newTable[i]; // newTable[i] => e.next
newTable[i] = e; // 将e => newTable[i]
e = next; // oldTable链减少一个节点继续遍历
}
}
}
// null放在table[0]位置
private V putForNullKey(V value) {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
// hash()
final int hash(Object k) {
int h = 0;
// if (useAltHashing) {
// if (k instanceof String) {
// return sun.misc.Hashing.stringHash32((String) k);
// }
// h = hashSeed;
// }
// hashCode()后二次散列，减少hash碰撞
h ^= k.hashCode();
/*
* 1. 扰动函数。核心思想使计算出的值在保留原有相关特性基础上，增加不确定性，从而降低冲突概率
* 2. 扰动函数，不同版本实现方式不一样，核心思想一致
* 3. 往右移动目的，将h的高位利用起来，减少哈西冲突
*/
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// mapping to index
static int indexFor(int h, int length) {
// 取模运算：h % length，取模效率不如位运算
return h & (length - 1);
}
static class Entry<K, V> {
int hash;
final K key;
V value;
Entry<K, V> next;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K, V> n) {
hash = h;
key = k;
value = v;
next = n;
}
void recordAccess(_HashMap7<K, V> m) {
}
}
@Override
public Set<Map.Entry<K, V>> entrySet() {
return null;
}
}
3. LinkedHashMap
- 唯一、有序（输入顺序）
extends HashMap<K,V>大部分方法走父类Entry<K, V> extends HashMap.Node<K, V>继承Node，增加双向链表指针
- 在HashMap基础上，维护双向链表
public class T4_LinkedHashMap {
/*
* 1. 唯一、有序（输入顺序）
* 2. `extends HashMap<K,V>`大部分方法走父类
* `Entry<K, V> extends HashMap.Node<K, V>`继承Node，增加双向链表指针
* 3. 在HashMap基础上，维护双向链表
*/
@Test
public void SC() {
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
Integer b = map.put("b", 2222);
System.out.println("b = " + b);
LinkedHashMap<String, Integer> mapArgs = new LinkedHashMap<>(10);
}
}
// extends HashMap<K, V>
class _LinkedHashMap<K, V> extends _HashMap8<K, V> implements Map<K, V> {
final boolean accessOrder;
public _LinkedHashMap() {
super();
accessOrder = false;
}
public _LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// 1. 添加元素 _HashMap8.put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 2. 添加元素情况处理 _HashMap8.putVal()
V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// ...
// 3. 新增子类节点。@Override
Node<K, V> tab = newNode(hash, key, value, null);
// ...
return null;
}
// 4. 创建新node，并维护双向链表
@Override
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
// 5.1.
_LinkedHashMap.Entry<K, V> p = new _LinkedHashMap.Entry<>(hash, key, value, e);
// 5.2.
linkNodeLast(p);
return p;
}
// 增加头、尾指针
transient _LinkedHashMap.Entry<K, V> head; // 头节点
transient _LinkedHashMap.Entry<K, V> tail; // 尾节点
// 维护head, tail
private void linkNodeLast(_LinkedHashMap.Entry<K, V> p) {
_LinkedHashMap.Entry<K, V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
// 增加before, after指针，维护双向链表
static class Entry<K, V> extends _HashMap8.Node<K, V> {
Entry<K, V> before, after;
Entry(int hash, K key, V value, Node<K, V> next) {
super(hash, key, value, next);
}
}
}
4. TreeMap
1. API
public class T5_TreeMap {
@Getter
@ToString
@AllArgsConstructor
static class Student implements Comparable<Student> {
Integer age;
String name;
@Override
public int compareTo(Student o) {
return this.getAge() - o.getAge();
}
}
/*
* 1. 唯一、有序（升序、降序、自定义顺序）
* 2. key
* 1. 二叉树，中序遍历
* 2. key为基本类型
* 3. key为自定义引用类型（Comparator）
*
*/
@Test
public void API() {
int present = 1;
TreeMap<Integer, Object> tmi = new TreeMap<>();
tmi.put(12, present);
tmi.put(3, present);
tmi.put(7, present);
tmi.put(9, present);
tmi.put(3, "present"); // 覆盖并返回value旧值
tmi.put(16, present);
// 1. 少一个 2. 升序 3. 覆盖并返回value旧值
System.out.println("tmi.size() = " + tmi.size());
System.out.println("tmi = " + tmi);
System.out.println("-----------------------------------------");
TreeMap<String, Object> tms = new TreeMap<>();
tms.put("e", present);
tms.put("b", present);
tms.put("a", present);
tms.put("d", present);
tms.put("c", present);
tms.put("d", present);
// 1. 少一个 2. 字母顺序
System.out.println("tms.size() = " + tms.size());
System.out.println("tms = " + tms);
System.out.println("--------------------- tm_inner ----------------------");
// 内部比较器
TreeMap<Student, Object> tm_inner = new TreeMap<>();
tm_inner.put(new Student(10, "e"), present);
tm_inner.put(new Student(8, "b"), present);
tm_inner.put(new Student(4, "a"), present);
tm_inner.put(new Student(9, "e"), present);
// 覆盖并返回value旧值
System.out.println("tmo.put(new Student(8, f)) = " + tm_inner.put(new Student(8, "f"), "ooxx"));
tm_inner.put(new Student(1, "d"), present);
System.out.println("tmo.size() = " + tm_inner.size());
System.out.println(tm_inner);
System.out.println("--------------------- tm_outer ---------------------");
// 外部比较器
Comparator<Student> com_stu = Comparator.comparingInt(Student::getAge).reversed();
TreeMap<Student, Object> tm_outer = new TreeMap<>(com_stu);
tm_outer.put(new Student(10, "e"), present);
tm_outer.put(new Student(8, "b"), present);
tm_outer.put(new Student(4, "a"), present);
tm_outer.put(new Student(9, "e"), present);
// 覆盖并返回value旧值
System.out.println("tmo.put(new Student(8, f)) = " + tm_outer.put(new Student(8, "f"), "ooxx"));
tm_outer.put(new Student(1, "d"), present);
System.out.println("tmo.size() = " + tm_outer.size());
System.out.println(tm_outer);
}
@Test
public void SC() {
TreeMap<String, Integer> map = new TreeMap<>();
map.put("ooxx", 1);
Comparator<Integer> com = Integer::compare;
TreeMap<Integer, Integer> args = new TreeMap<>(com);
}
}
2. SC
- 外部比较器
- 二叉树：
(左子树 < parent), (右子树 > parent) - 新增节点一定为叶子节点
fixAfterInsertion()=> 红黑树
class _TreeMap<K, V> {
// 1. 外部比较器
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K, V> root;
// 容器大小
private transient int size = 0;
private transient int modCount = 0;
private static final boolean RED = false;
private static final boolean BLACK = true;
// class Entry<K,V> implements Map.Entry<K,V>
static final class Entry<K, V> { // 二叉树结构
K key;
V value;
Entry<K, V> left;
Entry<K, V> right;
Entry<K, V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
// 覆盖oldValue，返回oldValue
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
}
// noArgsCtor。外部比较器 == null
public _TreeMap() {
comparator = null;
}
// argsCtor。指定外部比较器
public _TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 2. put()
// @Override Map
public V put(K key, V value) {
Entry<K, V> t = root;
// 2.1. 无root
if (t == null) {
// 自己跟自己比
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp; // 比较结果，确定parent的left，还是right
Entry<K, V> parent; // 元素parent
Comparator<? super K> cpr = comparator;
// 3. 找出插入元素的parent
// 3.1. 外部比较器
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); // 相等，覆盖，返回oldValue
} while (t != null);
}
// 3.2. 内部比较器
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); // 返回oldValue
} while (t != null);
}
// 4. 插入元素
Entry<K, V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 5. 红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
final int compare(Object k1, Object k2) {
return comparator == null ? ((Comparable<? super K>) k1).compareTo((K) k2)
: comparator.compare((K) k1, (K) k2);
}
private void fixAfterInsertion(Entry<K, V> x) {
// ...
}
}