HashMap的put和get方法介绍
相关集合介绍见:https://blog.csdn.net/fz13768884254/article/details/82905249
JAVA中的数组,在添加或者删除元素的时候,都会复制一个新数组,比较耗内存。但是数组的遍历则是非常高效的。链表则是相反,遍历慢(需要遍历数组,一直找到值相等的元素才算找到),而添加和删除元素代价低。
有没有办法结合两者的特点,做到寻找元素快,插入元素或者删除元素代价低呢?答案是利用哈利表。
HashMap put操作
当使用HashMap
的put
方法的时候,有两个问题要解决:
1、长度为16的数组中,元素存储在哪个位置
2、如果key
出现hash
冲突,如何解决
第一个问题,HashMap
是使用下面的算法来计算元素的存放位置的。
int hash = hash(key);
int i = indexFor(hash, table.length);
首先先hash
,之后结合数组的长度进行一个&操作得到得到数组的下标。
第二个问题 则利用Entry
类的next变量来实现链表,把最新的元素放到链表头,旧的数据则被最新的元素的next
变量引用着。
举个例子,假设元素Entry<"1","1">
通过hash
算法算出存到下标为0的位置上,后面又添加一个Entry<"2","2">
,
假设Entry<"2","2">
通过hash算法算出也需要存到下标为0的数组中,那么此时链表是下面这个样子的:
Entry<”2”,”2”> –> Entry<”1”,”1”>
也即是说,当key
出现hash
冲突的时候,链表中的第一个元素都是后面最新添加进来的那个,之前的则被next变量引用着。虽然这里是插入的动作,但是由于使用了链表,所以无需像数组的插入那样,进行数组拷贝。
HashMap get操作
这个操作的原理就比较简单,只需要根据key
的hashcode
算出元素在数组中的下标,之后遍历Entry
对象链表,直到找到元素为止。
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> 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;
}
这里有两个注意点:
1、这里利用key
的hashcode
方法和equals
方法,所以在使用HashMap
的时候,如果使用对象作为key,最好覆写key
的hashcode
和equals
方法
不然可能出put
到HashMap
的时候,成功了,但是get
的时候却没有找到数据
2、如果key
hash
冲突太多,会造成链表过长,在链表中查找元素的时候,会比较慢
扩展:hashMap的扩容机制和线程安全问题https://blog.csdn.net/fz13768884254/article/details/82905249