文档章节

Map接口与学习系列(二)---LinkedHashMap

alvaDing
 alvaDing
发布于 2016/09/10 10:47
字数 620
阅读 8
收藏 0
  • HashMap的实现是Hash表,健值对都是无序的。
  • TreeMap 的实现是红黑树结构,根据key排序,默认是升序,也可以自定义排序器的顺序
  • LinkedHashMap 保存了插入的顺序,保证输出的值与输入的顺序相同。
  • Hashtable 是同步的,有同步的开销。

HashMap是一个比较基础的Map的实现,HashMap的读取是无序和随机的。LinkedHashMap是继承自HashMap,并提供了HashMap没有的特性:保持数据的顺序读写,即可以根据输入的顺序输出。

TreeMap也可以保证顺序读写,TreeMap的底层数据结构是红黑树,读写的算法复杂度为O(logn),而LinkedHashMap的读可以达到O(1),在性能上面比TreeMap更好一些。

LinkedHashMap保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.在遍历的时候会比HashMap慢。

private transient Entry<K,V> header;
//accessOrder 标记是否为访问顺序,true是访问顺序,false为插入顺序,在初始化map的时候,默认为false
private final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}

在HashMap父类中定义了init方法,但实现是空的,在LinkedHashMap中实现如下:header链表初始化。

void init() {
    this.header = new LinkedHashMap.Entry(-1, (Object)null, (Object)null, (java.util.HashMap.Entry)null);
    this.header.before = this.header.after = this.header;
}

LinkedHashMap的put方法没有重写,采用的是父类的put方法,先看下HashMap.put()的源码:

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    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;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}
/**
 * Inserts this entry before the specified existing entry in the list.
 */
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

 

再次看下get方法的源码:

public V get(Object var1) {
    LinkedHashMap.Entry var2 = (LinkedHashMap.Entry)this.getEntry(var1);
//getEntry方法是使用父类HashMap的方法。
    if(var2 == null) {
        return null;
    } else {
var2不为空的时候,记录下写入顺序。
        var2.recordAccess(this);
        return var2.value;
    }
}
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

© 著作权归作者所有

alvaDing
粉丝 0
博文 10
码字总数 3248
作品 0
西安
程序员
私信 提问
java集合框架总结(一)

本系列博客详细介绍了JAVA集合框架,你将知道: 一.学习目标 1)java集合框架的层次结构 2)使用Collection接口定义的公用方法对集合和线性表操作 3)使用Iterator接口遍历集合 4)使用JDK的...

hapier
2016/09/01
73
0
集合(四): Map

更多实现类的源码分析请点击链接地址。。。。。。。 一: java.util.Map<k,v> Map用于保存具有映射关系的数据,因此Map集合(键值对的集合)里保存着两组值,一组值用于保存Map里的key,另外一...

牧羊人Berg
2016/06/14
46
0
Java集合 --- LinkedHashMap底层实现和原理(源码解析)

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedHashMap,见...

起个名忒难
2017/09/24
0
0
【JAVA】集合框架 学习笔记

以下是我学习java集合框架的笔记,内容主要是个人理解和网络视频、文章的摘录。 首先说一下什么是java集合框架,相信初学者刚开始听这个的时候,对于这个东西的概念是很模糊的。下面我用通俗...

qq_37792173
2017/09/11
0
0
java集合框架总结(六)

一、Map 简介 Map 用于保存具有映射关系的数据,因此 Map 集合里保存着两组值,一组值用于保存 Map 里的 Key,另外一组用于保存 Map 里的 Value Map 中的 key 和 value 都可以是任何引用类型...

hapier
2016/09/09
15
0

没有更多内容

加载失败,请刷新页面

加载更多

热点图heatMap.js V2.0 研究笔记 及应用

https://blog.csdn.net/rongchaoliu/article/details/47830799 调用方法 function init() { $.ajax({ url: "${request.contextPath}/refresh?type=1", type: "get",......

yan_liu
23分钟前
3
0
Kubernetes 支持 OpenAPI 的新功能

Open API 让 API 提供者可以定义自己的操作和模型,并让开发者可以自动化的生成喜欢语言的客户端,用以和 API 服务器通信。Kubernetes 已经支持 Swagger 1.2(OpenAPI 规范的前身)有一段时间...

xiangyunyan
27分钟前
0
0
深入分析Zookeeper原理

本章重点: 1.了解zookeeper 及zookeeper 的设计猜想 2. zookeeper集群角色 3. 深入分析ZAB协议 4. 从源码层面分析leader选举的实现过程 5. 关于zookeeper的数据存储  Zookeeper的由...

须臾之余
29分钟前
2
0
Spring Cloud Eureka 常用配置详解,建议收藏!

前几天,栈长分享了 《Spring Cloud Eureka 注册中心集群搭建,Greenwich 最新版!》,今天来分享下 Spring Cloud Eureka 常用的一些参数配置及说明。 Spring Boot 的配置参考Java技术栈微信...

Java技术栈
47分钟前
3
0
分布式项目(七)consul 服务注册与发现

说到分布式自然就离不开分布式和微服务的话题,简单聊一下。 微服务是一种软件架构方式,或者说一个一种结构设计风格,它并不是标准,它的逻辑是把一个整体服务按业务拆分成不同独立的服务,...

lelinked
48分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部