文档章节

Java集合:Map接口总结

阿阿阿阿阿局
 阿阿阿阿阿局
发布于 2016/08/08 23:34
字数 2409
阅读 40
收藏 3
点赞 0
评论 0

一、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往往是由外部负责整个应用初始化的代码来填充的。

 

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

© 著作权归作者所有

共有 人打赏支持
阿阿阿阿阿局
粉丝 12
博文 45
码字总数 61219
作品 0
成都
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

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

seaicelin ⋅ 05/25 ⋅ 0

Java编程学习:集合框架详解

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

Java小辰 ⋅ 05/30 ⋅ 0

Java面试2018常考题目汇总及答案带走不谢!

一、JAVA基础篇-概念 1.简述你所知道的Linux: Linux起源于1991年,1995年流行起来的免费操作系统,目前, Linux是主流的服务器操作系统, 广泛应用于互联网、云计算、智能手机(Android)等...

java高级架构牛人 ⋅ 06/14 ⋅ 0

Java编程基础知识点和技术点归纳

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

Java小辰 ⋅ 05/23 ⋅ 0

java集合入门和深入学习,看这篇就差不多了

集合框架: Java中的集合框架大类可分为Collection和Map;两者的区别: Collection是单列集合;Map是双列集合 Collection中只有Set系列要求元素唯一;Map中键需要唯一,值可以重复 Collecti...

sihailoveyan ⋅ 05/04 ⋅ 0

【java8】java新特性(二)——lambda表达式

一,前言 在上一篇博客中,小编向大家抛转引玉,简单说明了[ Java8 ](http://blog.csdn.net/kisscatforever/article/details/79572194 ),其实Java 8在2014年3月18日,就发布了。可以说程序...

kisscatforever ⋅ 03/20 ⋅ 0

2018年Java编程学习面试最全知识点总结

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

Java小辰 ⋅ 05/14 ⋅ 0

golang自定义路由控制实现(一)

    由于本人之前一直是Java Coder,在Java web开发中其实大家都很依赖框架,所以当在学习Golang的时候,自己便想着在Go开发中脱离框架,自己动手造框架来练习。通过学习借鉴Java的思想还...

1Day ⋅ 05/11 ⋅ 0

随机模拟 java 数据插件 - Jmockdata

Jmockdata ![License](http://www.apache.o

寻觅一只耳朵 ⋅ 2017/01/05 ⋅ 20

总结:深入浅出探索Java体系知识

前言 (1)编程:也就是人和计算机之间交流的过程,让计算机为解决某个问题而使用某种程序设计语言编写程序代码,并最终得到结果的过程。 (2)写代码的要诀:明确需求->分析思路->确定步骤-...

iwen-J ⋅ 04/07 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 19分钟前 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 28分钟前 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 37分钟前 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 50分钟前 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

到底会改名吗?微软GVFS 改名之争

微软去年透露了 Git Virtual File System(GVFS)项目,GVFS 是 Git 版本控制系统的一个开源插件,允许 Git 处理 TB 规模的代码库,比如 270 GB 的 Windows 代码库。该项目公布之初就引发了争...

linux-tao ⋅ 今天 ⋅ 0

笔试题之Java基础部分【简】【二】

1.静态变量和实例变量的区别 在语法定义上的区别:静态变量前要加static关键字,而实例变量前则不加。在程序运行时的区别:实例变量属于某个对象的属性,必须创建了实例对象,其中的实例变...

anlve ⋅ 今天 ⋅ 0

Lombok简单介绍及使用

官网 通过简单注解来精简代码达到消除冗长代码的目的 优点 提高编程效率 使代码更简洁 消除冗长代码 避免修改字段名字时忘记修改方法名 4.idea中安装lombnok pom.xml引入 <dependency> <grou...

to_ln ⋅ 今天 ⋅ 0

【转】JS浮点数运算Bug的解决办法

37.5*5.5=206.08 (JS算出来是这样的一个结果,我四舍五入取两位小数) 我先怀疑是四舍五入的问题,就直接用JS算了一个结果为:206.08499999999998 怎么会这样,两个只有一位小数的数字相乘,怎...

NickSoki ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部