认识达内从这里开始

hashmap是双链表格式的存储结构存储数据，没有顺序性，1.7基于hash表存储。允许空值存在，键中有且只允许有一个，值中也允许有空值存在。初始容量大小为16加载因子为0.75。

线程不安全，在并操作时存在安全问题。

常见操作解读

初始化new

初始化的时候无参情况下，使用默认初始大小和加载因子进行初始化。

//空参构造方法

public HashMap() {

this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

}

//构造方法

//执行构造方法之前会加载类中的变量

//初始化一个Entry对象数组

//transient Entry[] table = (Entry[]) EMPTY_TABLE;

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;

threshold = initialCapacity;

init();

}

添加操作

public V put(K key, V value) {

//是否为空Entry table

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

//key为null，hashMap专门空值设置一个存储方法

if (key == null)

return putForNullKey(value);

//计算hash

int hash = hash(key);

//计算index，根绝key的hash和table的长度

int i = indexFor(hash, table.length);

//是否有重复的key值，通过获取现有的table[i]是否为空来判断

//当不同key的hash值相同时为hash冲突，hash冲突时，需要便利所有的Entry比较是否key的==和equal方法一致。

//hash一致后Entry变为为链状，同一个index下有多个Entry[]数据，并把添加放置到重复index下的Entry中的最后一个

for (Entry e = table[i]; e != null; e = e.next) {

//重复key值处理

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

modCount++;

//添加Entry

addEntry(hash, key, value, i);

return null;

}

addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {

//当前entry的size大小大于threshold(size*0.75加载因子)并且当前表的index值已经存在

//散列表散列值计算，通常是两种方法：链表法和开放地址法

//链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

//1.7hashMap使用的就是链表法

if ((size >= threshold) && (null != table[bucketIndex])) {

//当大小超过threshold并且出现hash冲突的时候会扩容在不大于最大值的情况下是是旧表的二倍

resize(2 * table.length);

//是否重新计算hash

hash = (null != key) ? hash(key) : 0;

//给冲突的hash集合新表的长度再次计算hash

bucketIndex = indexFor(hash, table.length);

}

createEntry(hash, key, value, bucketIndex);

}

resize方法

void resize(int newCapacity) {

//旧表

Entry[] oldTable = table;

int oldCapacity = oldTable.length;

//如果已经是最大长度则直接返回

if (oldCapacity == MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return;

}

Entry[] newTable = new Entry[newCapacity];

//迁移表

transfer(newTable, initHashSeedAsNeeded(newCapacity));

table = newTable;

//重新计算 阀值

threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

}

threshold方法

void transfer(Entry[] newTable, boolean rehash) {

int newCapacity = newTable.length;

//遍历旧表对迁移新表

for (Entry e : table) {

//在对Entry链表的复制过程中可能会存在环的问题。多条线程并发操作，遍历Enrt表的时候会导致环的存在，新链表插入相比较旧链表而言是倒叙，因为多线程快慢问题可能导致。

//对有bucket链进行便利

while(null != e) {

//记录旧表的下一个entry值

Entry next = e.next;

//是否重新计算hash

if (rehash) {

e.hash = null == e.key ? 0 : hash(e.key);

}

//计算idex值

int i = indexFor(e.hash, newCapacity);

//新表的指针反转旧表指向

e.next = newTable[i];

//旧的enry携带新的指向赋值给新的槽位

newTable[i] = e;

//旧表指针往下

e = next;

}

}

}

获取

public V get(Object key) {

if (key == null)

return getForNullKey();

Entry entry = getEntry(key);

return null == entry ? null : entry.getValue();

}

getEntry方法

final Entry getEntry(Object key) {

if (size == 0) {

return null;

}

int hash = (key == null) ? 0 : hash(key);

//hash重复的情况

//比较key的equals和==的方法

for (Entry e = table[indexFor(hash, table.length)];e != null;e = e.next) {

Object k;

if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))

return e;

}

return null;

}

删除

public V remove(Object key) {

Entry e = removeEntryForKey(key);

return (e == null ? null : e.value);

}

removeEnryForKey方法

final Entry removeEntryForKey(Object key) {

if (size == 0) {

return null;

}

int hash = (key == null) ? 0 : hash(key);

int i = indexFor(hash, table.length);

//删除

Entry prev = table[i];

Entry e = prev;

while (e != null) {

Entry next = e.next;

Object k;

//hash相同时

if (e.hash == hash &&(k = e.key) == key || (key != null && key.equals(k)))) {

modCount++;

size--;

if (prev == e)

table[i] = next;

else

prev.next = next;

e.recordRemoval(this);

return e;

}

prev = e;

e = next;

}

return e;

}