文档章节

Java集合:Map接口总结

阿阿阿阿阿局
 阿阿阿阿阿局
发布于 2016/08/08 23:34
字数 2409
阅读 44
收藏 3

一、HashMap

  • 基于哈希表的 Map 接口的实现,允许存入 null 值和 null 键,无序存储且线程不同步;
  • HashMap 初始容量默认为16,扩容一定是2的指数,加载因子默认值为0.75; 
  • HashMap采用Iterator方式迭代,可直接迭代键值对;
  • 迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

建议多看源码,如果觉得晦涩可以戳这里看源码解析。

安利网址:http://www.admin10000.com/document/3322.html,个人觉得分析的挺好

 

JDK1.8+HashMap的改进

  • JDK1.8以前是采用的数组+链表形式存储,JDK1.8+是采用的是数组+链表/红黑树
  • JDK1.8+,当bucket节点数小于等于6时,转换为链表形式;当节点数大于等于8时,转换为红黑树形式

JDK1.8以前,HashMap的put()方法、get()源码如下:

put():

public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
    if (key == null)
        return putForNullKey(value);
    // 根据key的hashCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值所对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引处的Entry为null,表明此处还没有Entry。
    // modCount记录HashMap中修改结构的次数
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}

get():

public V get(Object key) {
		// 如果 key 是 null,调用 getForNullKey 取出对应的 value
		if (key == null)
			return getForNullKey();
		// 根据该 key 的 hashCode 值计算它的 hash 码
		int hash = hash(key.hashCode());
		// 直接取出 table 数组中指定索引处的值,
		for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null;
		// 搜索该 Entry 链的下一个 Entr
		e = e.next) // ①
		{
			Object k;
			// 如果该 Entry 的 key 与被搜索 key 相同
			if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
				return e.value;
		}
		return null;
	}

JDK1.8+,HashMap的put()、get()方法源码如下:

put():

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) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0,进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等,key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e,用e来记录
                e = p;
        // hash值不相等,即key不相等;为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 为链表结点
        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;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等,跳出循环
                    break;
                // 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

get():

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table已经初始化,长度大于0,根据hash寻找table中的项也不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 桶中第一项(数组元素)相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一个结点
        if ((e = first.next) != null) {
            // 为红黑树结点
            if (first instanceof TreeNode)
                // 在红黑树中查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 否则,在链表中查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

参考网址:

JDK1.8以前:http://www.cnblogs.com/xwdreamer/archive/2012/06/03/2532832.html

JDK1.8+:http://www.cnblogs.com/leesf456/p/5242233.html

二、Hashtable(小写t!!!)

  • 基于哈希表的 Dictionary 接口的实现,不允许存入 null 键和 null 值,无序存储且线程同步;
  • Hashtable采用的是Enumeration<T>迭代方式,key和value需要分别调用keys()和elements();
  • HashTable中hash数组默认大小是11,增加的方式是 oldCapacity * 2 + 1。
        Dictionary<String, String> dic = new Hashtable<String, String>();
		dic.put("zd", "zd");
		dic.put("age", "21");
		dic.put("zt", "zt");
		dic.put("age", "22");
		dic.put("sex", "girl");
		Enumeration<String> elemvalues = dic.elements();
		Enumeration<String> elemkeys = dic.keys();
		while(elemvalues.hasMoreElements() && elemkeys.hasMoreElements()){
			System.out.print(elemkeys.nextElement()+":");
			System.out.println(elemvalues.nextElement());
		}

更多详情看源码或戳这里

三、LinkedHashMap

  • LinkedHashMap继承于HashMap,不同于HashMap,采用的是双向链表方式实现,并且定义了迭代顺序,默认顺序为插入元素的顺序。
  • LinkedHashMap还提供了一个可以指定是默认排序(插入排序)还是按照访问排序的构造方法,如下:
    • public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
      • initialCapacity:初始容量,默认为16
      • loadFactor:装载因子,默认为0.75
      • accessOrder:true,按照访问排序;false,按照插入排序
        • 访问排序采用的是LRU最近最少使用的调度算法
  • HashMap可以向Entry的key和value存入null,LinkedHashMap也允许插入null键和null值。
  • 不是线程同步类。如果多线程同时访问LinkedHashMap,并且至少有一个线程会对其修改,则必须采用外部同步,如synchronized同步方法或synchronized同步块。还有种方法就是采用Collections工具类中的synchronizedMap()方法,如:
    • Map m = Collections.synchronizedMap(new LinkedHashMap(Object));

 LinkedHashMap默认为插入顺序排序,HashMap为无序:

public static void main(String[] args) {
		// TODO Auto-generated method stub
		Map<String, String> linkmap = new LinkedHashMap<String, String>();
		linkmap.put("zd", "zd");
		linkmap.put("age", "21");
		linkmap.put("sex", "girl");
		linkmap.put("zt", "zt");
		linkmap.put("age", "22");
		for(Entry<String, String> entry:linkmap.entrySet()){
			System.out.println(entry.getKey()+":"+entry.getValue());
		}
		System.out.println("===========================");
		Map<String, String> hashmap = new HashMap<String, String>();
		hashmap.put("zd", "zd");
		hashmap.put("age", "21");
		hashmap.put("zt", "zt");
		hashmap.put("age", "22");
		hashmap.put("sex", "girl");
		for(Entry<String, String> entry:hashmap.entrySet()){
			System.out.println(entry.getKey()+":"+entry.getValue());
		}
	}

结果展示:

更多详情看源码或者戳这里

三、ConcurrentHashMap

  • ConcurrentHashMap是since JDK1.5;
  • ConcurrentHashMap是线程同步的;
  • ConcurrentHashMap将数据分为多个segment,默认16个;
  • ConcurrentHashMap允许多个修改操作并发进行,因为每次只锁相应的segment,除类似size()和containsValue()方法等需要锁住整个hash表。

更多详情看源码或者戳这里

优秀博文:http://www.cnblogs.com/yydcdut/p/3959815.html

四、TreeMap

  • TreeMap通过红黑树算法实现;
  • TreeMap是有序的,可通过实现Comparator接口实现定制排序方式。

红黑树5点规定: 

  1. 每个节点都只能是红色或者黑色
  2. 根节点是黑色
  3. 每个叶节点(NIL节点,空节点)是黑色的。
  4. 如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

更多详情请戳这里,本人觉得讲的很详细,对红黑树也作了详细的阐述。

五、EnumMap

    EnumMap是专门为枚举类型量身定做的Map实现。虽然使用其它的Map实现(如HashMap)也能完成枚举类型实例到值得映射,但是使用EnumMap会更加高效:它只能接收同一枚举类型的实例作为键值,并且由于枚举类型实例的数量相对固定并且有限,所以EnumMap使用数组来存放与枚举类型对应的值。这使得EnumMap的效率非常高。

    提示:EnumMap在内部使用枚举类型的ordinal()得到当前实例的声明次序,并使用这个次序维护枚举类型实例对应值在数组的位置。

    下面是使用EnumMap的一个代码示例。枚举类型DataBaseType里存放了现在支持的所有数据库类型。针对不同的数据库,一些数据库相关的方法需要返回不一样的值,示例中getURL就是一个。

//现支持的数据库类型枚举类型定义

public enum DataBaseType{
    MYSQL,ORACLE,DB2,SQLSERVER
}

//DataBaseInfo类中定义的获取数据库URL的方法以及EnumMap的声明。

public class DataBaseInfo{
    private EnumMap<DataBaseType, String> urls = new EnumMap<DataBaseType, String>(DataBaseType.class);
    public DataBaseInfo(){
        urls.put(DataBaseType.DB2,"jdbc:db2://localhost:5000/sample");
        urls.put(DataBaseType.MYSQL,"jdbc:mysql://localhost/mydb");
        urls.put(DataBaseType.ORACLE,"jdbc:oracle:thin:@localhost:1521:sample");
        urls.put(DataBaseType.SQLSERVER,"jdbc:microsoft:sqlserver://localhost:1433;DatabaseName=mydb");
    }
}
/**
* 根据不同的数据库类型,返回对应的URL
* @param type DataBaseType枚举类新实例
*/
public String getURL(DataBaseType type){
    return this.urls.get(type);
}

在实际使用中,EnumMap对象urls往往是由外部负责整个应用初始化的代码来填充的。

 

该博文仅作为复习记录,大多数原理及源码解释已给出链接,优秀博客需要一起共赏。最后,若有错误,望纠正。

© 著作权归作者所有

共有 人打赏支持
阿阿阿阿阿局
粉丝 10
博文 48
码字总数 61219
作品 0
成都
私信 提问
JAVA基础再回首(三十)——JAVA基础再回首完美结束,感概万千!

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/m366917/article/details/52724939 JAVA基础再回首(三十)——JAVA基础再回首完美结束,感概万千! 经过了几...

Aduroidpc
2016/10/02
0
0
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin
05/25
0
0
kotlin学习笔记-异常好玩的list集合总结

不积跬步无以至千里,不积小流无以成江海 先看看Kotlin中for循环的遍历 kotlin和Java中的集合工具类 Java中集合及其工具类 Kotlin中Java中集合及其工具类 List MutableList Set MutableSet Ma...

codeGoogle
07/16
0
0
Java编程学习:集合框架详解

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰
05/30
0
0
jdk 5 到 jdk 10各个版本的新特性

jdk5 jdk10各个版本的新特性 JDK1.5新特性: 1.自动装箱与拆箱: 2.枚举 3.静态导入,如:import staticjava.lang.System.out 4.可变参数(Varargs) 5.内省(Introspector),主要用于操作J...

程序员诗人
03/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

apache顶级项目(二) - B~C

apache顶级项目(二) - B~C https://www.apache.org/ Bahir Apache Bahir provides extensions to multiple distributed analytic platforms, extending their reach with a diversity of s......

晨猫
47分钟前
0
0
day152-2018-11-19-英语流利阅读

“超级食物”竟然是营销噱头? Daniel 2018-11-19 1.今日导读 近几年来,超级食物 superfoods 开始逐渐走红。不难发现,越来越多的轻食餐厅也在不断推出以超级食物为主打食材的健康料理,像是...

飞鱼说编程
今天
3
0
SpringBoot源码:启动过程分析(二)

接着上篇继续分析 SpringBoot 的启动过程。 SpringBoot的版本为:2.1.0 release,最新版本。 一.时序图 一样的,我们先把时序图贴上来,方便理解: 二.源码分析 回顾一下,前面我们分析到了下...

Jacktanger
昨天
3
0
Apache防盗链配置,Directory访问控制,FilesMatch进行访问控制

防盗链配置 通过限制referer来实现防盗链的功能 配置前,使用curl -e 指定referer [root@test-a test-webroot]# curl -e "http://www.test.com/1.html" -x127.0.0.1:80 "www.test.com/1.jpg......

野雪球
昨天
3
0
RxJava threading

因为Rx针对异步系统设计,并且Rx也自然支持多线程,所以新的Rx开发人员有时会假设Rx默认是多线程的。在其他任何事情之前,重要的是澄清Rx默认是单线程的。 除非另有说明,否则每次调用onNex...

woshixin
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部