栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Map实现的双列集合

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Map实现的双列集合

 Map接口实现类体系图

 

 

HashMap和HashTable的异同
  • 继承的父类不同

       HashMap继承自AbstractMap类,Hashtable继承自Dictionary类,但二者都实现了Map接口。Dictionary类是一个已经被废弃的类(见其源码中的注释)。

  • 底层实现

       HashMap:Node[ ]数组+链表+红黑树

       HashTable: Entry[ ]数组+链表

        这里还要说一些东西,

        HashMap中新添加节点在某一索引位产生哈希冲突,会优先放置在链表的末尾,因为当链表达到一定长度就要变成红黑树,此后在该索引位新添加的节点就会根据树化方式放置在末尾

       HashTable中新添加的节点在某一索引位产生哈希冲突,会优先放置在链表的头节点,也就是说每次冲突都会让索引位先指向新添加的节点,而后让新添加节点内的next指针指向之前链表的头节点,完成后新添加的节点就会变成链表头节点。

  • 线程是否安全

        HashMap线程不安全

        HashTable线程安全

javadoc中关于hashmap的一段描述如下:

    此实现不是同步的。如果多个线程同时访问一个哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步。
    Hashtable 中的方法大多是Synchronize的,而HashMap中的方法在一般情况下是非Synchronize的。在多线程并发的环境下,可以直接使用Hashtable,不需要自己为它的方法实现同步,但使用HashMap时就必须要自己增加同步处理。HashTable实现线程安全的代价就是效率变低,因为会锁住整个HashTable,而ConcurrentHashMap做了相关优化,因为ConcurrentHashMap使用了分段锁,并不对整个数据进行锁定,效率比HashTable高很多。
   HashMap底层是一个Entry数组,当发生hash冲突的时候,hashmap是采用链表的方式来解决的,在对应的数组位置存放链表的头结点。对链表而言,新加入的节点会从头结点加入。

       hashmap的put方法调用putVal()方法,假如A线程和B线程同时对同一个数组索引位调用putVal()方法,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作,造成A的写入操作丢失。故解决方法就是使用ConcurrentHashMap。

      HashMap的迭代器(HashIterator)是fail-fast的,故当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException异。

 

       Hashtable的迭代器(enumerator)迭代器不是fail-fast的。但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。

  • 遍历方式

       HashMap只支持Iterator遍历,而HashTable支持Iterator和Enumeration两种方式遍历

  • contains方法,toString()方法

        HashMap是没有contains方法的,但有containsValue和containsKey方法,没有重写toString

        hashtable则保留了contains方法,同containsValue,并包括containsValue和containsKey方法,重写了toString()方法

  • 是否允许null值

       Hashmap是允许key和value为null值的,用containsValue和containsKey方法判断是否包含对应键值对;HashTable键值对都不能为空,否则报空指针异常。

  • 计算索引值方式

        为了得到元素的位置,首先需要根据元素的 KEY计算出一个hash值,然后再用这个hash值来计算得到最终的位置。

        ①:HashMap有个hash()方法重新计算了key的hashCode,目的是为了有效避免hash冲突:

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

        注意这里计算hash值,先调用hashCode方法计算出一个hash码,再将hash码与右移16位的hash码相异或,从而得到新的hash值。

       在求hash值对应的位置索引时,index = (n - 1) & hash。将哈希表的大小固定为了2的幂,因为是取模得到索引值,故这样取模时,不需要做除法,只需要做位运算。位运算比除法的效率要高很多。
        ②:Hashtable通过key的hashCode()方法得到的hash值就为最终hash值。

        在求hash值位置索引时计算index的方法:

int index = (hash & 0x7FFFFFFF) % tab.length;

     &0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数

     因此hashtable的哈希冲突概率会比hashmap高很多

  • 默认初始容量,个性化初始容量

       HashMap 的初始容量为:16,Hashtable 初始容量为:11。两者的默认负载因子都是0.75。 

       这里有一点也要注意, HashMap有tableSizeFor()方法,而HashTable没有该方法,因此: 

       对于  HashMap,如果自定义初始容量>=0,最后哈希表的容量为比自定义容量大并且最接近自定义容量的2的n次幂,如果自定义初始容量<0,则会报错

      对于  HashTable,如果自定义初始容量>0,则容量是啥就是啥,之后除非扩容,否则不会改变。如果自定义初始容量=0,则之后容量会设置为1。如果自定义初始容量<0,则会报错

 

  •  是否懒加载

 HashMap只有在首次调用putVal方法添加元素,本质上就是调用resize()方法,才会new一个堆空间,让table指向堆空间,因此是懒加载

HashTable在调用构造方法时,就会new一个堆空间,让table指向堆空间,因此不是懒加载

  • 扩容方式不同

        HashMap 容量不足时要调用resize()方法,Hashtable容量不足时要调用rehash()方法
        HashMap 扩容必须要求为原容量的2倍,而且容量一定是2的n次幂,而Hashtable扩容为原容量2倍+1;

  • 解决hash冲突方式不同

       HashMap:

  • 如果冲突数量小于8,则是以链表方式解决冲突。
  • 而当冲突大于等于8时,就会将冲突的Node转换为红黑树进行存储。
  • 而当数量小于6时,则又转化为链表存储。

      HashTable:

  •  都以链表方式存储

TreeMap

这里的排序是指按照一定的规则将添加进集合的元素按一定顺序放置。而hashmap元素的放置完全由hash值决定,因此放置是无序的。但是遍历的时候,hashmap由hash table的索引位从小到大遍历,索引位有链表,优先遍历链表中的元素。

  • 概述
  1. TreeMap存储K-V键值对,通过红黑树(R-B tree)实现;

  2. TreeMap继承了NavigableMap接口,NavigableMap接口继承了SortedMap接口,可支持一系列的导航定位以及导航操作的方法,当然只是提供了接口,需要TreeMap自己去实现;
  3. TreeMap实现了Cloneable接口,可被克隆,实现了Serializable接口,可序列化;
  4. TreeMap因为是通过红黑树实现,红黑树结构天然支持排序,默认情况下通过Key值的自然顺序进行排序;
  • 成员变量和成员内部类

       我们先看一下TreeMap中主要的成员变量

private final Comparator comparator;
 

private transient Entry root;
 

private transient int size = 0;
 

private transient int modCount = 0;

        上面的成员变量根节点root指向Entry类的实体,我们来看一下内部类Entry的源码

static final class Entry implements Map.Entry {
        K key;
        V value;
        Entry left;
        Entry right;
        Entry parent;
        boolean color = BLACK;

        
        Entry(K key, V value, Entry parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        
        public K getKey() {
            return key;
        }

        
        public V getValue() {
            return value;
        }

        
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

       Entry静态内部类实现了Map的内部接口Entry,提供了红黑树存储结构的java实现,通过left属性可以建立左子树,通过right属性可以建立右子树,通过parent可以往上找到父节点。

       大体的实现结构图如下:

  • 构造函数
//默认构造函数,按照key的自然顺序排列
public TreeMap() {comparator = null;}
//传递Comparator具体实现,按照该实现规则进行排序
public TreeMap(Comparator comparator) {this.comparator = comparator;}
//传递一个map实体构建TreeMap,按照默认规则排序
public TreeMap(Map m) {
    comparator = null;
    putAll(m);
}
//传递一个map实体构建TreeMap,按照传递的map的排序规则进行排序
public TreeMap(SortedMap m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

LinkedHashMap
  • 简介

       LinkedHashMap继承了HashMap类,是HashMap的子类,LinkedHashMap的大多数方法的实现直接使用了父类HashMap的方法。LinkedHashMap可以说是HashMap和LinkedList的集合体,既使用了HashMap的数据结构,又借用了LinkedList双向链表的结构。

  • 结构体系

 

       我们看到LinkedHashMap中定义了一个Entry静态内部类,定义了5个构造器,一些成员变量,如head,tail,accessOrder,并继承了HashMap的方法,同时实现了一些迭代器方法。我们先看一下Entry类

static class Entry extends HashMap.Node {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

       我们看到这个静态内部类很简单,继承了HashMap的Node内部类,我们知道Node类是HashMap的底层数据结构,实现了数组+链表/红黑树的结构,而Entry类保留了HashMap的数据结构,同时通过before,after实现了双向链表结构(HashMap中Node类只有next属性,并不具备双向链表结构)。那么before,after和next到底什么关系呢。

       看上面的结构图,定义了头结点head,当我们调用迭代器进行遍历时,通过head开始遍历,通过before属性可以不断找到下一个,直到tail尾结点,从而实现顺序性。而在同一个hash(在上图中表现了同一行)链表内部after和next效果是一样的。不同点在于before和after可以连接不同hash之间的链表。

       前面我们发现数据结构已经完全支持其顺序性了,接下来我们再看一下构造方法,看一下比起HashMap的构造方法是否有不同。

// 构造方法1,构造一个指定初始容量和负载因子的、按照插入顺序的LinkedList
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 构造方法2,构造一个指定初始容量的LinkedHashMap,取得键值对的顺序是插入顺序
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 构造方法3,用默认的初始化容量和负载因子创建一个LinkedHashMap,取得键值对的顺序是插入顺序
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 构造方法4,通过传入的map创建一个LinkedHashMap,容量为默认容量(16)和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者,装载因子为默认值
public LinkedHashMap(Map m) {
    super(m);
    accessOrder = false;
}
// 构造方法5,根据指定容量、装载因子和键值对保持顺序创建一个LinkedHashMap
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

       我们发现除了多了一个变量accessOrder之外,并无不同,此变量到底起了什么作用?

       通过注释发现该变量为true时access-order,即按访问顺序遍历,如果为false,则表示按插入顺序遍历。默认为false。在哪些地方使用到该变量了,同时怎么理解?

  • 三个重要的方法
      1.putVal方法

         LinkedHashMap的put方法沿用了父类HashMap的put方法,LinkedHashMap的Entry类就是继承了HashMap的Node类。同样的,HashMap的put方法中调用的其他方法在LinkedHashMap中已经被重写,运行时执行子类重写的方法,这就是动态绑定。

         putVal的源码在此省略。。。

      2.newNode()方法

         LinkedHashMap重写了newNode()方法,通过此方法保证了插入的顺序性

Node newNode(int hash, K key, V value, Node e) {
        LinkedHashMap.Entry p = new LinkedHashMap.Entry<>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

//LinkedHashMap类中的成员变量tail和head:

//The head (eldest) of the doubly linked list.
transient LinkedHashMap.Entry head;
//The tail (youngest) of the doubly linked list.
transient LinkedHashMap.Entry tail;


// link at the end of list
    private void linkNodeLast(LinkedHashMap.Entry p) {
        LinkedHashMap.Entry last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

        简单描述以上代码:首次添加元素时,head和tail指针都指向null,因此首次执行linkNodeLast方法后,head和tail指针都指向第一个元素,before指针和after指针仍指向null。当不是首次执行linkNodeLast方法,说明head指针指向首次添加的元素,last指针指向上次添加的元素,tail重定向到这次添加的元素,随后新添加元素p的before指针指向last指针,也就是指向上次添加的元素,上次添加元素的after指针指向新添加元素p。通过此方法实现了双向链表功能。

      3.afterNodeAccess()方法

       关于afterNodeAccess()方法,在HashMap中没给具体实现,而在LinkedHashMap重写了,目的是保证操作过的Node节点永远在最后,从而保证读取的顺序性,在调用put方法和get方法时都会用到。

void afterNodeAccess(Node e) {
    //在执行方法前的上一次的尾结点
    LinkedHashMap.Entry last;
    //当accessOrder为true并且传入的节点并不是上一次的尾结点时,执行下面的方法
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)e, b = p.before, a = p.after;
        //p:当前节点
        //b:当前节点的前一个节点
        //a:当前节点的后一个节点;
        
        //将p.after设置为null,断开了与后一个节点的关系,但还未确定其位置
        p.after = null;
        
        if (b == null)
            head = a;
        else
            b.after = a;
        
        if (a != null)
            a.before = b;
        else
            last = b;
        
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        //最后节点p设置为尾结点,完事
        tail = p;
        ++modCount;
    }
}

      但是afterNodeAccess方法是否执行是可以控制的,由accessOrder是否为真决定,实际上调用前文提到的构造方法5即可个性设置accessOrder

if (accessOrder && (last = tail) != e)
  • accessOrder==false
LinkedHashMap map = new LinkedHashMap<>(16, 0.75f, false);
map.put("1月", 20);
//此时就会调用到linkNodeLast()方法,也会调用afterNodeAccess()方法,但会被阻挡在
//if (accessOrder && (last = tail) != e) 之外
map.put("2月", 30);
map.put("3月", 65);
map.put("4月", 43);
//这时不会调用linkNodeLast(),会调用afterNodeAccess()方法将key为“1月”的元素放到最后
map.put("1月", 35);
map.get("2月");
//调用打印方法
for (Map.Entry entry : map.entrySet()){
    System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}

result:
key: 1月, value: 35
key: 2月, value: 30
key: 3月, value: 65
key: 4月, value: 43
  • accessOrder==true
LinkedHashMap map = new LinkedHashMap<>(16, 0.75f, true);
map.put("1月", 20);
//此时就会调用到linkNodeLast()方法,也会调用afterNodeAccess()方法,但会被阻挡在
//if (accessOrder && (last = tail) != e) 之外
map.put("2月", 30);
map.put("3月", 65);
map.put("4月", 43);
//这时不会调用linkNodeLast(),会调用afterNodeAccess()方法将key为“1月”的元素放到最后
map.put("1月", 35);
//这时不会调用linkNodeLast(),会调用afterNodeAccess()方法将key为“2月”的元素放到最后
map.get("2月");
//调用打印方法
for (Map.Entry entry : map.entrySet()){
    System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}

result:
key: 3月, value: 65
key: 4月, value: 43
key: 1月, value: 35
key: 2月, value: 30

       大家看到区别了吗,accessOrder为false时,你访问的顺序就是按照你第一次插入的顺序;而accessOrder为true时,你任何一次的操作,包括put、get操作,都会改变map中已有的存储顺序。

  • afterNodeInsertion方法

        我们看到在LinkedHashMap中还重写了afterNodeInsertion(boolean evict)方法,它的目的是移除链表中最老的节点对象,也就是当前在头部的节点对象,但实际上在JDK8中不会执行,因为removeEldestEntry方法始终返回false。看源码:

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
protected boolean removeEldestEntry(Map.Entry eldest) {
    return false;
}
  • get方法

        LinkedHashMap的get方法与HashMap中get方法的不同点也在于多了afterNodeAccess()方法

public V get(Object key) {
    Node e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
  • remove()方法

        remove方法也直接使用了HashMap中的remove,在HashMap章节并没有讲解,因为remove的原理很简单,通过传递的参数key计算出hash,据此可找到对应的Node节点,接下来如果该Node节点是直接在数组中的Node,则将table数组该位置的元素设置为node.next;如果是链表中的,则遍历链表,直到找到对应的node节点,然后建立该节点的上一个节点的next设置为该节点的next。

public V remove(Object key) {
        Node e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
}


final Node removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node[] tab; Node p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

void afterNodeRemoval(Node e) {
    LinkedHashMap.Entry p = (LinkedHashMap.Entry)e, b = p.before, a = p.after;
    //将待删除节点的before和after都设置为null
    p.before = p.after = null;
    
    if (b == null)
        head = a;
    else
        b.after = a;
    
    if (a == null)
        tail = b;
    else
        a.before = b;
}

         LinkedHashMap重写了其中的afterNodeRemoval(Node e),该方法在HashMap中没有具体实现,通过此方法在删除节点的时候调整了双链表的结构

ConcurrentHashMap、HashTable、HashMap区别 1、HashMap

因为多线程环境下,使用Hashmap进行put操作可能会引起死锁,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。【PS:HashMap 是允许key值为空的】

2、HashTable

Hashtable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下Hashtable的效率非常低下。因为当一个线程访问Hashtable的同步方法时,其他线程访问Hashtable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。

3、ConcurrentHashMap

1)jdk7版本

ConcurrentHashMap和HashMap设计思路差不多,但是为支持并发操作,做了一定的改进,ConcurrentHashMap引入Segment 的概念,目的是将map拆分成多个Segment(默认16个)。操作ConcurrentHashMap细化到操作某一个Segment。在多线程环境下,不同线程操作不同的Segment,他们互不影响,这便可实现并发操作。

2)jdk8版本

jdk8版本的ConcurrentHashMap相对于jdk7版本,发送了很大改动,jdk8直接抛弃了Segment的设计,采用了 较为轻捷的Node + CAS + Synchronized设计,保证线程安全。

3)总结

1、get方法不加锁;

2、put、remove方法要使用锁

jdk7使用锁分离机制(Segment分段加锁)

jdk8使用cas + synchronized 实现锁操作

3、Iterator对象的使用,运行一边更新,一遍遍历(可以根据原理自己拓展)

4、复合操作,无法保证线程安全,需要额外加锁保证

5、并发环境下,ConcurrentHashMap 效率较Collections.synchronizedMap()更高

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956457.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号