4.Map
4.1.介绍
- Map是Map集合体系的顶级接口
- Map所存储的数据, key-value结构的数据, 键值对
- Map的key不允许’’重复’’:
- Key-value数据具有自我描述性(用key来描述value)
- Map继承体系：
- Map
- AbstractMap接口
- HashMap
- LinkedHashMap
- TreeMap
- HashMap
- SortedMap类
- NavigableMap类
- Hashtable(线程安全)
- Dictionary
- AbstractMap接口
- Map
4.2.常用方法
-
public void clear()：从此映射中移除所有映射关系（可选操作）。
-
public boolean equals(Object o)：比较指定的对象与此映射是否相等。
-
public int hashCode()：返回此映射的哈希码值。
-
public boolean isEmpty()：如果此映射未包含键-值映射关系，则返回 true。
-
public int size()：返回此映射中的键-值映射关系数。
-
public V put(K key, V value)：将指定的值与此映射中的指定键关联（可选操作）。
-
public void putAll(Map<? extends K,? extends V> m)：从指定映射中将所有映射关系复制到此映射中（可选操作）。
-
public V remove(Object key)：如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。
-
public V get(Object key)：返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。
-
public boolean containsKey(Object key)：如果此映射包含指定键的映射关系，则返回 true。
-
public boolean containsValue(Object value)：如果此映射将一个或多个键映射到指定值，则返回 true。
-
public Set<Map.Entry<K,V>> entrySet()：返回此映射中包含的映射关系的 Set 视图。
-
public Set keySet()：返回此映射中包含的键的 Set 视图。
-
public Collection values()：返回此映射中包含的值的 Collection 视图。
4.3.HashMap
4.3.1.特点
- hashmap的底层结构 : 数组 + 链表 + 红黑树 (jdk 1.8)，(jdk1.8之前: 没有红黑树, 就是数组 + 单链表)
- hashmap底层维护了一个数组
- 数组默认初始容量16 , 数组扩容机制: 每次扩为原来的2倍, 默认的加载因子是0.75
- 无序(这个顺序是对key计算哈希值并对数组长度取余后，存储的数组索引位置为先后顺序)
- 不允许重复的key，如果重复，则新值替换旧值
- 允许存储null键, 0
- 线程不安全
- Hashmap能存储的元素数量 <= 底层数组长度 * 加载因子的
- hashmap怎么判断重复的问题：(hash是否一样 && (key直接相等 || key相equals ))，Hash = (h = key.hashCode()) ^ (h >>> 16)
- 可以用构造方法传入初始容量，但是会向上取为2的n次方
- 如果key是一个引用变量的话，不要使用引用来修改它的内容，因为这样会无法再次找到，除非再次修改回原来的key的内容
- 链表转化为红黑树，只有该散列位置存储的结点数量超过8，并且新添加的值是第9个的时候，才会转化为红黑树
- 红黑树转化为链表只有两种情况，删除或扩容，删除的时候可能会导致结点满足判断条件触发反树化，判断条件见源码分析，扩容可能会导致，hash对新容量2n取余以后，散列位置修改为x+n的情况，从而使得原来的散列位置存储的结点分散开存储，链表长度小于6，同样触发反树化，
- 如果当链表长度超过8达到9的时候，同样也不一定会树化
- 链表长度小于64，优先扩容而不是树化
- 链表长度大于等于64，必定会由链表转化为红黑树
4.3.2.HashMap源码分析
- HashMap的初始容量、扩容机制、判断null键的部分源码分析
//HashMap的构造方法
HashMap<String, String> map = new HashMap<>();
map.put("zs", "18");
map.put("ls", "18");
//HashMap源码分析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//定义的默认初始容量，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//定义的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//底层维护的数组，Node是它的存储结点的键值对类型
transient Node<K,V>[] table;
//存储的键值对个数
transient int size;
//加载因子
final float loadFactor;
//标记阈值
int threshold;
//无参构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//当调用put添加方法的时候，再调用一个putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//先计算key的hash值，再将参数传入
static final int hash(Object key) {
int h;
//这里，为保证尽力避免hash碰撞，调用hashcode方法以后再移位16位取异或运算
//本质目的还是为了尽可能的让返回的hashcode值的所有数字都参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//判断添加值的相关方法，其中hash就是key的hash值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //数组
Node<K,V> p; //结点
int n, i;
//判断底层数组是否为null，重复判断
if ((tab = table) == null || (n = tab.length) == 0)
//调用扩容方法，给n赋值为16
n = (tab = resize()).length;
//p = tab[i] ，其中i=(hash对(n-1))取余数，计算数组下标位置
//如果这个散列位置为空，那么执行下边的语句
//(n - 1) & hash 本质上是hash值对n取余，位运算是为了运算速度
if ((p = tab[i = (n - 1) & hash]) == null)
//把这个新结点赋值给tab[i]，即把这个值存进去
tab[i] = newNode(hash, key, value, null);
else { //如果这个值已经存在了
//一个结点，一个key值
Node<K,V> e; K k;
//如果，hash值相等，且，key相等或者(key不是null且相equals)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//把p赋值给e
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;
//添加完了的时候，元素数量+1，如果他大于了阈值，那么就调用扩容方法
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//上个函数中用到的的resize()扩容方法
final Node<K,V>[] resize() {
//底层数组，初始时刻为null，当第一次超过阈值的时候就是16了
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //0，超过阈值后为16
int oldThr = threshold; //0，超过阈值后为12
int newCap, newThr = 0;
if (oldCap > 0) { //初始状态不会执行，超过阈值会执行
if (oldCap >= MAXIMUM_CAPACITY) { //不可能大于等于的，这个值非常大
threshold = Integer.MAX_VALUE;
return oldTab;
}
//超过阈值后执行这里，把新容量扩容为旧容量的二倍，即32，小于最大值的，也是大于默认值16的
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新阈值是旧阈值的二倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//执行这里，给newCap赋值为16
newCap = DEFAULT_INITIAL_CAPACITY;
//新阈值为 0.75 * 16 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//不执行
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 初始threshold = 12
// 第二次threshold = 24
threshold = newThr;
//创建了一个16个长度的数组
//再次创建一个二倍大小的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//table是一个16长度的数组
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
//内部类，用于存储元素的结点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final 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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
}
- HashMap的带参构造方法部分源码分析
//带参构造方法
HashMap<String, String> map = new HashMap<>(20);
map.put("zs", "18");
//对于以上代码，源码分析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16; //到此，变为大于cap参数的最小的 2的n次方-1 的数字，即11111111......
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; //返回一个2的n次方的数，即32
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
}
//扩容方法
final Node<K,V>[] resize() {
//null
Node<K,V>[] oldTab = table;
//初始为空，旧容量为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧阈值为2的n次方，在这里为32
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { oldCap = 0 , 假
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 旧阈值大于0，旧阈值赋值给新容量，即32
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//新阈值只声明，默认为0，真
if (newThr == 0) {
//ft = 32 * 0.75 = 24
float ft = (float)newCap * loadFactor;
//新容量是否小于最大值，小于，ft小于是否小于最大值，小于，则新容量为24
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//阈值为24
threshold = newThr;
//创建一个为32长度的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//把底层数组赋值为创建的32容量的数组
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
}
- HashMap链表—>红黑树部分源码分析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static final int TREEIFY_THRESHOLD = 8;
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;
//p=tab[i]已经赋值了，相当于某个下标位置的链表的根节点
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;
//判断p是不是红黑树的根节点
else if (p instanceof TreeNode)
//如果是，按红黑树的比较逻辑进行比较
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果程序走这个分支，那么说明存储元素是单链表
for (int binCount = 0; ; ++binCount) {
//e是存储位置的根节点的下一个结点
//只有当链表数量达到8的时候，这时候第9个还是空，e就是空了，进入该if语句
if ((e = p.next) == null) {
//把新值赋给p.next
p.next = newNode(hash, key, value, null);
//binCount>=7的时候，触发
//但是，binCount是从0开始计数的，所以执行到第8次循环，才会树化
//同时，e在每次if判断都会赋值为p.next，在for循环最后，p=p.next
//所以，最后应该是，链表长度超过8达到9，并且第9个是新添加的元素的时候，才会触发树化操作
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=p.next
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//替换value
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//树化的函数，不做重点
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
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;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
}
- HashMap红黑树—>链表的部分源码分析，删除导致的反树化
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
public V remove(Object key) {
Node<K,V> e;
//true参数就是反树化的参数
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//获得要删除的红黑树结点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
//删除找到的红黑树结点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
//root方法，不断查找父节点，直到找到根节点，见下
root = root.root();
//此时，root是根节点
//这个条件，说明，root是空，或者，
//(removeNode函数的传入的参数movable为真 && (root.right为空 || (root.left为空 || root.left.left为空)))判断条件是真
if (root == null
|| (movable//传入的参数
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
//树太小了，反树化，红黑树转化成链表
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
//removeTreeNode方法中的root方法
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
//不断查找父节点，直到没有父节点，即根节点
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
- HashMap红黑树—>链表的部分源码分析，扩容导致的反树化
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static final int UNTREEIFY_THRESHOLD = 6;
//扩容方法
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//上面都在创建一个新数组，与赋值底层数组没什么关系
//下面就是，把旧数组的数据转移到新数组中去
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//e赋值为散列位置的根节点
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果e是树的结点的话，拆分到新数组中去，拆分成两部分，一个是原来位置，一个是原来位置+原来的数组长度
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
//树的拆分函数
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//遍历拆分，一个拆分到之前的位置，一个拆分到新的位置
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//与容量取与运算，因为容量的二进制表示形式一定是1000...，所以如果相与后，结果全为0，那么肯定是旧位置
//如果相与后，结果是1000....，那么肯定是新位置
//留在原来位置的结点
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
//留在新位置的结点
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//原位置和新位置的判断，是否需要反树化(存储的元素不多了)
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) //6
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
}
- 当链表长度大于8达到9的时候，是否一定会转化为红黑树
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static final int MIN_TREEIFY_CAPACITY = 64;
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;
}
//判断是否树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果底层数组是空(一般不可能)，或者底层数组长度小于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;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
}
- 关于使用引用修改引用类型键值无法删除的问题
//定义一个User类型
class User{
String name;
String age;
public User(String name, String age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return Objects.equals(name, user.name) &&
Objects.equals(age, user.age);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return "{" +
"n='" + name + '\'' +
", a='" + age + '\'' +
'}';
}
}
//测试一下通过引用修改索引后的remove函数
public class TestHashMap {
public static void main(String[] args) {
HashMap<User, String> map = new HashMap<>();
User zs = new User("zs", "18");
//计算一下zs对象的散列位置，索引为14
int hash1 = (hash1 = zs.hashCode()) ^ (hash1 >>> 16);
int index1 = hash1 % 16;
System.out.println(index1);
map.put(zs, "1");
//map内容为{{n='zs', a='18'}=1}
System.out.println(map);
//修改zs对象的name属性为ls，此时map内容为{{n='ls', a='18'}=1}
zs.name = "ls";
System.out.println(map);
//修改后，zs的散列位置为0
int hashChange = (hashChange = zs.hashCode()) ^ (hashChange >>> 16);
int indexChange = hashChange % 16;
System.out.println(indexChange);
//试图移除zs对象，在散列位置0已经找不到zs对象了，所以无法移除
map.remove(zs);
System.out.println(map);
//修改回zs的name属性为zs
zs.name = "zs";
System.out.println(map);
//新建一个对象ls，内容和zs对象一样
User ls = new User("zs", "18");
//ls的散列位置也是14
int hash2 = 0;
hash2 = (hash2 = ls.hashCode()) ^ (hash2 >>> 16);
int index2 = hash2 % 16;
System.out.println(index2);
//检验一下源码中的remove函数中的equals判断方法
System.out.println(zs.equals(ls));
//可以移除，因为源码中判断二者相等equals方法已经重写了，想删除也可以通过clear方法清空map的内容
//User对象中，重写后的hashcode方法参数为User的属性，所以二者散列位置也相同，可以找到并删除
map.remove(ls);
//map内容已经为空
System.out.println(map);
}
}
//如果不重写hashcode和equals方法，那么即使通过引用修改内容也可以移除，因为Object中的hashcode方法是通过引用变量的地址来计算hashcode值的。
//所以即使修改了引用变量中的内容，该引用类型地址也没有发声改变，因此仍然能找到该引用类型，同理equals方法也相同。
//但是，在实际应用中，只要map中存储了引用变量，该引用类型必须要重写hashcode和equals方法的。即我们所认知的内容相同就是相同。
4.4.LinkedHashMap
- LinkedHashMap是HashMap的子类，基本特点和HashMap一样。
- LinkedHashMap是有序的，因为其结点中存储了before引用和after引用，其地层结构在HashMap基础上又维护了一个双向链表
- LinkedHashMap一个特殊的构造方法
- public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)：构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
- 对于该构造方法，accessOrder参数如果为true，LinkedHashMap中的内容顺序会随着访问顺序而改变(最近访问的会移到最后)
- public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)：构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
- LinkedHashMap部分源码分析
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
//LinkedHashMap中的newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
//LinkedHashMap中的内部类，继承了HashMap中的Node内部类
static class Entry<K,V> extends HashMap.Node<K,V> {
//双向链表
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
}
//LinkedHashMap中并没有put方法，因此，在添加结点的时候只是复用了HashMap中的put方法
//但是，在添加新结点调用newNode方法时，因为子类中有重写后的，所以应该是调用子类的
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
}
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final 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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
}
4.5.TreeMap
- 基本特点
- 他是Map的一个树(红黑树)实现
- 底层结构是红黑树
- 大小有序
- 不能存储’’重复’’元素key(自然顺序的重复)
- 不允许存储null键
- 线程不安全
- 如果使用默认的无参构造方法, 要求存储的元素的key, 应该实现 ‘自然顺序’(实现Comparable接口，重写compareTo方法)
- 如果在TreeMap中存储的元素, 没有实现 “自然顺序”, 那么TreeMap如果提供了比较器(Comparator)也是可以比较的
- 如果比较器和自然顺序同时存在, 优先使用比较器
- 常用方法
- public Map.Entry<K,V> ceilingEntry(K key)：返回一个键-值映射关系，它与大于等于给定键的最小键关联；如果不存在这样的键，则返回 null。
- public K ceilingKey(K key)：返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。
- public Comparator<? super K> comparator()：返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。
- public NavigableSet descendingKeySet()：返回此映射中所包含键的逆序 NavigableSet 视图。
- public NavigableMap<K,V> descendingMap()：返回此映射中所包含映射关系的逆序视图。
- public Set<Map.Entry<K,V>> entrySet()：返回此映射中包含的映射关系的 Set 视图。
- public Map.Entry<K,V> firstEntry()：返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
- public K firstKey()：返回此映射中当前第一个（最低）键。
- public Map.Entry<K,V> floorEntry(K key)：返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null。
- public K floorKey(K key)：返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。
- public V get(Object key)：返回指定键所映射的值，如果对于该键而言，此映射不包含任何映射关系，则返回 null。
- public SortedMap<K,V> headMap(K toKey)：返回此映射的部分视图，其键值严格小于 toKey。
- public NavigableMap<K,V> headMap(K toKey, boolean inclusive)：返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。
- Map.Entry<K,V> higherEntry(K key)：返回一个键-值映射关系，它与严格大于给定键的最小键关联；如果不存在这样的键，则返回 null。
- public K higherKey(K key)：返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。
- public Set keySet()：返回此映射包含的键的 Set 视图。
- public Map.Entry<K,V> lastEntry()：返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。
- public K lastKey()：返回映射中当前最后一个（最高）键。
- public Map.Entry<K,V> lowerEntry(K key)：返回一个键-值映射关系，它与严格小于给定键的最大键关联；如果不存在这样的键，则返回 null。
- public K lowerKey(K key)：返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。
- public NavigableSet navigableKeySet()：返回此映射中所包含键的 NavigableSet 视图。
- public Map.Entry<K,V> pollFirstEntry()：移除并返回与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
- public Map.Entry<K,V> pollLastEntry()：移除并返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。
- public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)：返回此映射的部分视图，其键的范围从 fromKey 到 toKey。
- public SortedMap<K,V> subMap(K fromKey, K toKey)：返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。
- public SortedMap<K,V> tailMap(K fromKey)：返回此映射的部分视图，其键大于等于 fromKey。
- public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)：返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。
4.6.HashTable
- 特点
- 是一个线程安全的Map实现(jdk1.0的一个产物)
- 底层结构: 数组 + 链表 ( 和HashMap在1.8之前的底层结构一模一样)
- 默认的初始容量: 11
- 给定初始容量: 底层数组就是给定值
- 扩容: 扩为原来长度的2倍+1
- Hash计算: 经过%取余, 效率略低
- HashTable部分源码分析
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
public Hashtable() {
this(11, 0.75f);
}
//默认传入参数，初始容量为11，加载因子为0.75
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
// 底层数组
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
//......
//索引计算，用取余的方法
index = (hash & 0x7FFFFFFF) % tab.length;
//......
//扩容，新容量是旧容量的2倍再+1
int newCapacity = (oldCapacity << 1) + 1;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/181077.html
