黑马程序员技术交流社区

标题: Map集合概述 [打印本页]

作者: 缘來是妳 时间: 2017-12-4 16:21
标题: Map集合概述
[size=10.5000pt]
一、Map概述
[size=10.5000pt]

Map是一种映射表，也称为关联数组，它已键值对的方式来存储数据，所有你可以使用键来查找到值。在Map集合中，键和值都可以是引用类型的，键一般不重复，如果重复，则后一个添加的键值对会覆盖已存在集合中的那个键值对，所有Map中一个键所对应的值是唯一的。

二、Java标准类库中Map的几种实现：

图片1.png (288.95 KB, 下载次数: 13)

下载附件

2017-12-4 16:10 上传

三、散列与散列码：
散列和散列码就是为了速度而存在的。
Map中元素并不是直接存储在集合中的，而是以桶(可以理解为一个键值对)的方式存储在一些桶位中。在Map集合的底层，是以数组(散列表)来存储元素的，散列表就是用来存储桶位的，而每个桶位中又可以存储很多个桶，这些桶也是以数组的形式存储在集合中的。

散列码就是将键的hashCode产生的值经过一系列处理后的int数值，而这些数值就是数组的索引。散列就是在这些以散列码为索引的每一个桶位上的元素所组成的一个数组，散列的分布是由散列码来决定的。

以HashMap为例：

图片3.png (52.39 KB, 下载次数: 19)

下载附件

2017-12-4 16:12 上传

在HashMap中通过将键的hashCode方法产生的hash值进行二次哈希，并模与散列表的长度以保证每一个元素都能正确的放入到集合的桶位中。经过计算后会产生相同的散列码，在通过查找元素时，也是以同样的方法计算key的哈希值，来缩小要查询的范围，从而实现快速查询，所以HashMap中元素的存储和查询的开销是固定的。HshMap中允许存储null键，而null键总是位于散列表的第一个位置。

四：Map的几种常用的实现的特点

HashMap：如前面描述的那样，HashMap就是为了提高速度而使用散列和散列码的方式来存储元素，插入和查询的开销都是固定的，也可以根据具体情况来调节集合的容量和负载因子，来进一步提高集合的性能。

LinkedHashMap：HashMap的直接子类，在HashMap的基础上保持了元素插入和取出的顺序。LinkedHashMap中以链表的形式维护了键的顺序，在遍历时会从链表的顶端依次将元素取出。在其构造器中可以设定采用最近最少使用(LRU) 算法，其结果就是最近最少使用的元素会出现在集合的最前端，如果不在需要可以选择删除元素，以提高集合的性能。

TreeMap：基于红黑树的实现，元素在集合中会以一种方式进行排序，为了实现排序功能，元素必须实现Compareable接口，重写compareTo方法，以指定元素以那种方法进行排序。

WeakHashMap、ConcurrentHashMap和IdentifyHashMap在此不具体说明，有兴趣的可以上网查询相关资料。
文章从《Think in java》中总结，如有理解错误，还望大家指正！

作者: 奥斯托洛夫斯基 时间: 2017-12-4 17:59