java·数据结构·hashMap
特点
- 线程不安全
- HashMap、和Hashtable、SynchronizedMap区别:
- HashMap 线程不安全,可以有null的key值或value值。
- hashtable 线程安全,不能有null的key值或value值。
- ConcurrentHashMap 线程安全,不能有null的key值或value值。删除操作比较费时。
- SynchronizedMap 线程安全,可以有null的key值或value值。
- 可以通过
Collections.synchronizedMap(new HashMap<String, Object>())
方式创建
- 可以通过
- 性能:HashMap>ConcurrentHashMap>SynchronizedMap>Hashtable
构造方法
相关参数
- initialCapacity:初始最大容量,默认1<<4(2^4),内部实际使用的变量是threshold(默认容量) ,实际最大容量并没有存放。
- loadFactor:加载因子(默认容量=初始最大容量*加载因子),默认0.75
- threshold:默认容量,内部变量,根据initialCapacity生成。执行构造方法时,将输入的initialCapacity转为不小于当前数的最小的2^k的值,作为threshold。在第一次构建table时(第一次put(实际上时putVal方法),执行resize()方法),table的大小设置为threshold,然后让threshold = threshold * loadFactor;后续每一次resize,都是table的大小 = table的大小 * 2;threshold = threshold * 2;
- 默认关系:threshold = initialCapacity * loadFactor(达到最大容量时不满足该等式)
平衡与折衷
- 加载因子:hash表中元素的填满程度,加载因子越大,空间利用率越高,冲突机会越高(查询成本越高)
代码解析
- public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
/**初始最大容量为非负整数*/
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
/**
* static final int MAXIMUM_CAPACITY = 1 << 30;
* 当 initialCapacity 大于最大容量(2^30,约10.74亿)时,强制设置为容量为最大容量。
*/
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
/**
* 加载因子为大于0的浮点数
* public static boolean isNaN(float v) {
* return (v != v);
* }
* Float.isNaN(loadFactor):NaN(not-a-number),例如. float v = 0.0f/0.0f;
*/
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
/**赋值容量因子*/
this.loadFactor = loadFactor;
/**
* 转换输入的初始最大容量为2^k,赋值给threshold作为实际最大容量
* 这样做的意义待分析
*/
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 获取不小于当前数的最小的2^k的值.
* 例如:31->32,65->128
*/
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;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- public HashMap(int initialCapacity)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- public HashMap()
/**
* 在resize()方法中设置threshold的值
* newCap = DEFAULT_INITIAL_CAPACITY;
* newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- public HashMap(Map<? extends K, ? extends V> m)
- Map<String,Object> map = new HashMap<>(); Map.putAll(mapEntries);
=>(完全等价于)
Map<String,Object> map = new HashMap<>(mapEntries);
(LinkedHashMap 继承于HashMap,该场景不一定完全等价,区别在于afterNodeInsertion方法,待梳理)
- Map<String,Object> map = new HashMap<>(); Map.putAll(mapEntries);
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
/**
* 当传入的map映射中存有对象时,进行插入逻辑
*/
if (s > 0) {
/**
* table == null ,这时threshold = 0,需要进行设置threshold的值,tableSizeFor方法作用可见上文。
*/
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
/**
* 如果传入的映射中对象个数大于当前默认容量,容量扩大1倍
* (put方法中已经有resize逻辑,该操作的意义待分析)
*/
else if (s > threshold)
resize();
/**
* 循环遍历每一个对象进行插入操作,和put方法完全一样
*/
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
put
相关参数
- 暂未梳理
hashcode
- hashcode(Object)只和物理地址有关,和对象的内容没有关系。
class Student {
String name;
String[] likes;
public Student(String name){
this.name = name;
}
public Student(String name,String[] likes){
this.name = name;
this.likes = likes;
}
}
System.out.println(new Student("a").equals(new Student("a")));//false
Student aa = new Student("a");
System.out.println(aa.hashCode());//1410986873
aa.name = "bcdefg";
System.out.println(aa.hashCode());//1410986873
aa.name = "a";
System.out.println(aa.hashCode());//1410986873
Student bb = new Student("a",new String[] {"爱好1","爱好2"});
System.out.println(bb.hashCode());//2110245805
bb.likes = new String[] {"爱好1","爱好4"};
System.out.println(bb.hashCode());//2110245805
HashMap<String, Object> hashMap2 = new HashMap<String, Object>(1 << 4);
for(int i=0;i<13;i++) {
hashMap2.put(String.valueOf(i), 1);
}
System.out.println(hashMap2.hashCode());//5228
HashMap<String, Object> hashMap3 = new HashMap<String, Object>(1 << 4);
for(int i=0;i<13;i++) {
hashMap3.put(String.valueOf(i), 1);
}
System.out.println(hashMap3.hashCode());//5228
System.out.println(((Object)hashMap2).equals(hashMap3));//true
- hashMap.hashcode对hashcode方法进行了重写,和key、value的hashcode有关系
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
static class Node<K,V> implements Map.Entry<K,V> {
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
}
public final class Objects {
public static int hashCode(Object o) {
return o != null ? o.hashCode() : 0;
}
}
public class Object {
/**
* 生成一个int类型的整型
* 1.同一个对象(未发生变化)只能生成一个hashcode,如果equals(Object的equals方法),那么hashcode一定相等。
* 2.不同对象可能会生成一个hashcode
* 3.Object的hashCode方法只和物理地址有关,和对象的内容没有关系。
*/
public native int hashCode();
}
代码解析
- static final int hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- final Node<K,V>[] resize()
/**
* 初始化或者给table容量加倍
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
/**
* 旧的最大容量,初始化时为0
*/
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)
//非处初始化操作,oldCap>=16时,thr已经很规范了,直接二倍即可。
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);
}
//初始化操作时newThr == 0,非处初始化操作,但oldCap<16时,通过cap和factor生成thr。
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
/**
* 代码到这里的时候,结构已经扩增完成了,得到了最终的threshold和table结构
*/
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
/**
* 将oldTab的值拷贝到newTab中
*/
//table非null,性能优化
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
/**
* 为什么在for循环内new对象,是否性能更高?
*/
Node<K,V> e;
//内容非null,性能优化
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//通过e的hash值和当前最大容量来确定一个唯一的hash值?简单推测
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//红黑树?待梳理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve orde
//对链表结构的处理
//低位组low
Node<K,V> loHead = null, loTail = null;
//高位组high
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/**
* key为null,e.hash=0
* 初始化时oldcap = 0
*/
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;
}
- public V put(K key, V value)
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;
}
小结:
- java位运算相关知识待归纳。 (位运算的目的是提高效率)
- 1 << k(2^k)
- ^是异或运算符,异或的规则是转换成二进制比较,相同为0,不同为1.
- int c=a ^ b ; a=c ^ b;b=c ^ a;
- a&b 的操作的结果:a、b中对应位同时为1,则对应结果位也为1
- double和float区别待归纳。
- LinkedHashMap、HashMap、treemap、treenodes关系
- 为什么n初始化构造map时,转换输入的初始最大容量为2^k,赋值给threshold作为实际最大容量。
相关文章