前言

Map是一个和Collection接口同辈分的接口.他的实现类中能够存储具有k-v映射关系的元素.这里将对Map集合中的HashMap,Hashtable,ConcurrentHashMap,TreeMap实现类做一定分析,加深一下对Map集合的理解.

Map接口

1 2	//map接口定义如下 public interface Map<K,V>

map只是一个接口,里面定义了一些map实现类都所具有的公共方法,Map接口常用的子类有如下四个

HashMap
Hashtbale(并不是我写错了哦.他确实没有按照驼峰命名法)
TreeMap
ConcurrentHashMap

HashMap

HashMap是一种基于散列表形式,能够存放k-v结构元素的集合

HashMap的内部结构

HashMap的内部是数组+链表的形式,数组的每个单元称作桶,通过哈希值决定键值对在这个数组的寻址.哈希值相等的值在同一个桶中以链表的形式串联在一起.需要的是,当链表的阈值,也就是链表的长度大于8的时候,链表会进行树化,变成一棵红黑树
hashmap结构图:

HashMap的基本概念

首先数组的优点在于查找数据的时候可以在O(1)的时间复杂度下精确快速的查找到想要的元素,所以为了查找方便hashmap底层首先使用了一个数组维护插入的数据,数组的每一个单元叫做桶.
hashMap中插入的数据不同于普通数据,而是一种k-v结构的数据,就不多说了.数据插入的时候也不像普通数组那样直接按序插入,而是通过一种 hash散列 的方式插入数据.具体方式就是,插入数据的坐标 o(散列值) 等于插入元素的key值的hash值再对数组长度取余.即 hash值(散列值) o=hash(key)%len,例如上图,key值为12, 28,108的数据在一个桶内

//默认数组初始长度是16,并规定必须是2的倍数   
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//JDK源码中计算hash值的方法
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

此时出现了一个问题.那就是当插入的数据越来越多,肯定会出现o值相同的情况.那么此时对应数组下标的位置就需要存储不止一个数据.这种情况就称为hash冲突.
解决hash冲突的方法有很多种,hashMap在设计上使用了 拉链法 解决hash冲突.当有多个key值相同的数据时,会在对应的数组下标处由第一个插入的数据开始维护一个链表.一旦有相同散列值的k-v数据就全部在链表后面串联起来.当链表的长度( 阈值 )大于8时,自动转变为一颗红黑树.

1 2	//jdk树化链表节点的阈值 static final int TREEIFY_THRESHOLD = 8;

源码证明:
1.hashmap中数组存放的是k-v形式的数据

//数组的定义   
transient Node<K,V>[] table;

//Node节点(只截取了一部分源码)
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

2.hashmap中数组table[]的初始化使用的是懒加载机制.数组并没有在构造方法中就初始化,而是在第一次数据插入的时候进行初始化

1
2
3

 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

这种数据结构的优点就在于数据的插入,删除,查询都是先通过散列值找到对应的桶的位置,然后在桶中的链表中进行添加,删除,和单纯的数组相比,大大提高了插入,删除的效率.和单纯的链表相比,又大大提高了查询的效率

HashMap中元素的插入即负载因子的概念

插入方法put(k,v)的全部源码如下

//① 当我们使用外部的插入接口时,内部调用的是该方法
public V put(K key, V value) {
        //但实际上真正完成插入操作的是该重载方法  
        return putVal(hash(key), key, value, false, true);
}
 
//② 真正完成插入操作的方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab代表hashmap的数组,p代表要插入桶中的节点,n是数组长度,i 计算出的数组下标  
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        /**首次插入数据的时候会进行判断
        /将table值赋值给tab如果当前tab的引用为空且长度也为空,证明hashmap类中的table[] 属性还没有被初始化   
        此时调用resize()方法,进行数组的输出化,并计算数组长度赋值给n  
        **/
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //进行hash运算,判断桶中是否为空,如果为空,当前插入对象为该桶中的首节点元素   
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        /**如果桶不为空,即发生了hash碰撞,拉链法解决hash冲突
        有如下几种情况  
        **/
        else {
            //e是一个临时节点 k存放当前对象的key值
            Node<K,V> e; K k;
            //情况1:插入的 k-v的 hash值和 key值都和当前节点的相同,e=p,表示为首节点  
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //情况2:插入的节点不是首节点,判断插入的节点是否是红黑树的一个节点
            else if (p instanceof TreeNode)
                //是红黑树节点进行插入,成功返回null,如果该节点存在就返回该节点  
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //情况3:插入节点不为首节点,不为红黑树节点,则为链表中节点
            else {
                //遍历链表
                for (int binCount = 0; ; ++binCount) {
                    //如果找到尾节点,证明节点没有重复.尾尾插就好
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //此处判断是否要转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果发现有相同的节点,e则为当前重复的节点,直接跳出
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //有重复的值,则用待插入值进行覆盖  
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
         //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null
        ++modCount;
        //真正的数组长度+1
        if (++size > threshold)
            //当数组长度大于临界值,需要进行扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

以上是put操作的具体实现,但是有一个问题,当数组扩容之后,所有的数据迁移到新的数组的时候,由于数组的长度发生了变化,那么根据hash函数,此时所有数据的插入位置也应该会发生新的变化,此时需要改变k-v对的索引值,这个过程也就是总有人获得”rehash的过程”,但实际上没有对所有数据的key重新进行hash计算,只需要看看原来的hash值高位新增的那个bit是1还是0，是0的话索引不变，是1的话索引变成“原索引+oldCap”;

负载因子
可能看完上面之后知道了当数组容量到达一定值的时候会进行数组resize(),数组扩容,但是仔细一想,好像还是不知道到底多大的值才是数组需要扩容的值,这里有一个负载因子的概念.

1	static final float DEFAULT_LOAD_FACTOR = 0.75f;

hashmap源码中负载因子的默认值为0.75,这个值的大小决定了数组什么时候扩容
在hashmap中规定了一个数组大小的临界值loadFactor,当数组的长度大于这个临界值的时候数组就会进行扩容

/**
    * The load factor for the hash table.
    *
    * @serial
    */
   final float loadFactor;

而这个临界值是由负载因子决定的
临界值的大小为数组的长度*负载因子的大小

1	threshold = (int)(capacity * loadFactor);

比如说数组的长度如果为16,那么等到数组中的实际元素个数大于 16 x 0.75 = 12的时候,数组就会进行扩容
需要知道的是扩容操作是一个十分消耗资源的操作.应该尽量减少可能进行扩容的机会

用自定义类型作为HashMap的key需要注意哪些问题

map的遍历不能直接使用迭代器,因为他没有直接继承Iterator接口,所以需要先把map集合转变为set集合,然后在使用迭代器
map中提供了一个entrySet()方法把一个map转变为一个set,具体使用看下面代码

首先看下使用JDK中的类型作为key插入时的情况

public class Test {

    public static void main(String[] args) {

        HashMap<String,Integer> map = new HashMap<String, Integer>();
        map.put("aaa",123);
        map.put("aaa",456);

        Set<Map.Entry<String,Integer>> set =  map.entrySet();
        Iterator iterator  = set.iterator();
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry)iterator.next();
            System.out.println(entry.getKey()+"--"+entry.getValue());
        }
    }
}

输出结果:

aaa--456

可以看到在插入时检测到了重复的键值,然后将value做了覆盖
在看看如果自定义一个类,然后使用自定义类的对象作为键值时的情况

class People{
    private Integer id;
    private String name;

    public People(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "People{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

public class Test2 {

    public static void main(String[] args) {
        Map<People,String> map = new HashMap<People, String>();
        People people1 = new People(1,"张三");
        People people2 = new People(1,"张三");
        map.put(people1,"北京");
        map.put(people2,"上海");
        Set<Map.Entry<People,String>> set = map.entrySet();
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry) iterator.next();
            System.out.println("key= "+entry.getKey()+" - "+"value= "+entry.getValue());
        }
    }
}

结果:

1 2	key= People{id=1, name='张三'} - value= 上海 key= People{id=1, name='张三'} - value= 北京

此时明明插入的数据相同,但是却没有进行覆盖,而是被当作两个不同的对象存储在了hashmap中,为什么会造成这种情况呢?

首先说一下具体插入时,hashmap是怎么判断是否是重复的key值当一个新的k-v对准备插入的时候,首先会对这个k值进行hash运算.具体是先计算这个k值的hashcode.然后得到hash值,去数组中找hash值的位置是否存在元素.如果不存在则直接插入,存在的话使用eqauls方法和该桶中后面的key依次比较,如果有相同的就进行值的覆盖,如果没有相同的,就插入到链表的末尾

之所以我们自定义的类在插入时即使看起来一样也被当作了不同对象的原因在于类定义时没有覆盖hashcode方法,所以hashmap在进行hashcode运算时会直接调用Object类提供的hashcode方法,这是一个本地方法,他计算hashcode值只与对象本身有关,即我们new了两个对象,虽然名字一样,但是实际上是两个不同的对象(因为对象的地址都不相等),所以计算出来的hashcode总是不同的.而我们希望的是根据创建对象的name属性来判断是不是同一个对象.所以就应该覆写hashcode方法,让他来根据name字符串来计算hashcode值.在覆写equals方法,因为原方法比较的是两个对象的地址,无论怎么比肯定也不一样.现在需要根据id来比较两个对象是否是同一个对象.所以也要覆写,具体做法如下

//同时覆写hashcode和equals  
@Override
    public int hashCode() {
        return id.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        People people = (People)obj;
        if(people.id.equals(this.id)){
            return true;
        }else{
            return false;
        }
    }

此时在看结果

1	key= People{id=1, name='张三'} - value= 上海

第一个k-v对被覆盖掉了
修改过后在插入时hash值的计算会根据对象的id来计算,所以只要是一个id,计算出来的hash值肯定相等,然后在链表中对象比较时使用equals方法,比较的是两个对象id的内容相等,如果还想等,就证明是重复元素,直接进行覆盖

Hashtable

Hashtable,就是常听说的散列表,也是Map接口的一个子类,他推出的时间在JDK1.0,他的实现基本和HashMap相同,但是在某些方面HashMap对其作了优化.此处主要从两者的区别入手介绍一个Hashtable

HashMap是Hashtable的一个轻量级实现,HashMap中可以存储空的键(key),值(value),键或者值都可以为null,也可以同时为空;Hashtable不可以存储空的键值,任意一个为null都不行
Hashtable是线程安全的,他里面的方法都有被synchronized修饰;HashMap是线程不安全的.所以HashMap的执行效率是要比Hashtable高的
Hashtable需要使用Enumeration遍历.HashMap使用Iterator遍历
在Hashtable中数组的默认大小为11,增加的方式是old*2+1.在HashMap中数组的默认大小是16,增加的方式是2的次方式增加
hash值的计算方法不同,Hashtable中hash值直接为key的hashcode,而HashMap中还要经过一些运算.

ConcurrentHashMap

前面说过HashMap是线程不安全的,当多个线程同时操作一个HashMap时,如果一条线程处此时HashMap正好正在进行扩容操作,但另外的几个线程是不知道的,他们仍然在进行put操作,此时如果hash值相等,可能出现在同一数组下用链表表示,从而造成闭环,导致在get的时候出现死循环.所以说HashMap是线程不安全的.
而Hashtable是线程安全的,他在所有涉及多线程的操作上都加上了synchronized锁住整个table(数组),这就意味着所有线程都在竞争一把锁,在多线程的环境下,他是安全的,但是无疑也是低效的.
为了解决多线程下的安全问题,便出现了ConcurrentHashMap.他的底层实现和HashMap基本相同,但是他加入了保证多线程下安全操作的方法并且优化了Hashtable的做法

ConcurrentHashMap加锁机制

JDK1.7下的ConcurrentHashMap
Hashtable之所有效率比较低下是因为在进行带锁的操作时,该锁锁住的是整个Hashtable中的数组,但是他进行插入的部分也就只是某一个桶.这就导致其他桶的操作也要停下来等待获取锁.
于是ConcurrentHashMap中使用锁分离的思想,将一个大锁分为许多的小锁,原来一个锁锁住的是整个table,现在把table分为许多小的table,每个小的table有自己的一把锁,操作对应的小table只需要获取相应的锁就好.
以此便提高了多线程下操作的效率,这就是锁分离技术,将锁的粒度降低,利用多个锁控制多个小的table

ConcurrentHashMap的内部结构
在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示

Segment数组的意义就是将一个大的table分割成的多个小的table来进行加锁,也就是上面说到的锁分离技术,每一个Segment元素存储的是一个数组+链表,这个和HashMap是相同的.需要注意的是,1.7种ConcurrentHashMap使用的锁是Lock锁
JDK1.8下的ConcurrentHashMap
在JDK1.8中基本摒弃了Segment的概念,而是采用Node数组+链表+红黑树的形式实现ConcurrentHashMap,并发控制使用synchronized关键字+CAS操作,整个看起来就像是一个经过优化并且能够保证线程安全的HashMap.
相比较1.7,再次降低了锁的粒度,不再像1.7中那样对部分数组加锁,而是直接给某一个行的第一个元素进行加锁.并且把1.7种数组+链表的形式改为了数组+链表+红黑树

treeMap

该类也是Map接口中的一个实现类,但是他的底层没有像他的兄弟姐妹那样使用数组+链表,TreeMap的底层是一颗红黑树…树的节点都是k-v形式的元素
他是一个可以排序的Map子类,默认的排序方法是根据key的内容排序.之所以能够进行排序是因为他实现了Comparable接口.
如果想要自定义的使TreeMap中的元素排序,那么就要覆写Comparable接口中的compareTo方法,不再需要覆写equals和hashcode