对HashMap的思考

前言

HashMap是一个散列表,它存储的内容是==Key-Value==键值对的映射。

类原型如下:

继承自抽象类AbstractMap,实现Map接口,Cloneable主要是用于clone方法,以及序列化接口。

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {

Map的常用类型

enter description here
继承Map接口的有以下几种:

  • HashMap:根据键的HashCode值进行数据的存储,可以直接根据键获取值,访问速度很快。是非同步的,即线程不安全。==key和value都可以为null,但是只能有一个为null的key,value无限制。==
  • TreeMap:能够根据底层的红黑二叉树来对插入的数据按照==key==进行从小到大的排序。且其key不能为null,value可以为null。==key为null时,在代码编写阶段不会报错,但运行时报NullPointerException。==同时TreeMap非同步的,线程不安全。
  • HashTable:HashTable的key与value是不能为null,且和HashMap最大的区别是HashTable是线程安全的,其方法都是有==synchronized==关键字修饰的,其继承自==Dictionary==。但是不建议使用,因为并发不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。
  • LinkHashMap:采用的是链表的方式存储数据,使用Iterator进行遍历的时候,先得到的是最先插入的,即==保留了记录的插入顺序==,和HashMap的底层实现不同,导致使用LinkHashMap的时候的遍历效率比HashMap慢。同时key和value都可以为null,非同步,线程不安全。

HashMap的JDK1.6\1.7实现

在JDK1.6,1.7中,HashMap采用的是数组+链表的方式,即使用数组存放链表。同一个HashCode值的元素都是存储在一个链表里面,但是如果位于同一个链表的元素(就是HashCode值相等的元素)增多的时候,查找元素的时候就不能很好的发挥HashMap的功效了。

enter description here

如图:

当调用map的put方法放入key-value键值对,那么首先会根据key的hashCode值,计算出在给定的key在数组中的位置,然后放在其后的单链表中。

这样的设计的好处是减少了Hash碰撞,即HashCode值相同并不一定意味着对象是相同的。那么这些HashCode怎么转化为数组空间的呢?一般是hash(key)%length来得到的。

疑问

1、如果多个key通过hashCode%length这样的算法得到的index都是相同的,会不会被覆盖?

不会。当A通过计算得到index=1,放在链表中,如果接下来来了一个B,B通过计算得到的index也=1,那么做的事情就是使用头插法将新来的元素插入到链表的头结点。为什么使用头插法呢?可能是觉得新来的元素被查找的概率要高一点吧,毕竟查找是从头开始。

2、HashMap是允许存入key-value为null的Entry的,那么他们在什么位置呢?

null key总是放在entry的第一个元素。

3、get操作原理

get的函数原型如下:public V get(Object key),先根据key的HashCode定位到数组的index,然后在这个index位置的链表进行遍历。

HashMap在JDK1.8的实现

在JDK1.8之后,也许是意识到了当链表长度过长带来的遍历效率的问题,因此,在JDK1.8中最重要的变化之一就是引入了红黑树,当同一个hash值的节点数不小于8时,不再采用单链表形式存储,而是采用红黑树。

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。

有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。

HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。

如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。

常用API

clear() 从 Map 中删除所有映射
remove(Object key) 从 Map 中删除键和关联的值
put(Object key, Object value) 将指定值与指定键相关联
putAll(Map t) 将指定 Map 中的所有映射复制到此 map
entrySet() 返回 Map 中所包含映射的 Set 视图。Set 中的每个元素都是一个 Map.Entry 对象,可以使用 getKey() 和 getValue() 方法(还有一个 setValue() 方法)访问后者的键元素和值元素
keySet() 返回 Map 中所包含键的 Set 视图。删除 Set 中的元素还将删除 Map 中相应的映射(键和值)
values() 返回 map 中所包含值的 Collection 视图。删除 Collection 中的元素还将删除 Map 中相应的映射(键和值)
get(Object key) 返回与指定键关联的值
containsKey(Object key) 如果 Map 包含指定键的映射,则返回 true
containsValue(Object value) 如果此 Map 将一个或多个键映射到指定值,则返回 true
isEmpty() 如果 Map 不包含键-值映射,则返回 true
size() 返回 Map 中的键-值映射的数目
-------------The End-------------

本文标题:对HashMap的思考

文章作者:Dimple

发布时间:2018年08月09日 - 09:08

最后更新:2018年09月28日 - 17:09

原始链接:http://www.bianxiaofeng.com/2018/08/09/2018-08-09-09-29-20/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

na,给我一个棒棒糖!
0%