前言

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

类原型如下:

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

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

Map的常用类型


继承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 中的键-值映射的数目 |