HashMap为Map接口基于数组+链表的实现类,以Key-Value形式进行存储,可以根据hash算法来计算Key-Value的值
构造函数
HashMap有三个构造函数
HashMap():构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity):构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor):构造一个带指定初始容量和加载因子的空 HashMap。
其中初始容量和加载因子的设置会影响hashMap的性能,初始容量就是创建是哈希表的容量,加载因子为哈希表在是否需要扩容的一个尺度
认识Entry
在创建HashMap时,都会初始化一个数组,而数组的元素为Entry,Entry为HashMap的一个内部类
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } }
Entry内部类包含key、value、下一个节点以及hash值
HashMap的put方法
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } //hashmap允许一个key为空值,保存key为value的值 if (key == null) return putForNullKey(value); //计算key的hash值 int hash = hash(key); //查找hash所在table的位置 int i = indexFor(hash, table.length); //找出要保存的位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //是否有hash值相同的(key相同),如果存在相同,则直接覆盖value,返回旧value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //不存在进行保存 addEntry(hash, key, value, i); return null; }
HashMap的get方法
读比较简单,通过key的hash值找到在table数组中的索引处的Entry
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }
jdk1.8的HashMap相对于jdk1.7略有不同,在链表越来越长时,会造成Hash严重冲突,查询效率降低,
所以在jdk1.8引入了红黑树
线程安全的ConcurrentHashMap
jdk1.7
由Segment数组、HashEntry组成,和HashMap组成相同,唯一的区别就是其中的核心数据如 value ,以及链表都是 Volatile 修饰的,保证了获取时的可见性
其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,ConcurrentHashMap 采用了分段锁技术
jdk1.8
删掉Segment分段锁,用node数组+链表+红黑树的数据结构实现,引入CAS (CAS:会不断地去比较当前内存中的变量值与你指定的一个变量值是否相等,如果相等,则接受你指定的修改的值,否则拒绝你的操作)+synchronized 来保证并发安全性