Java提高篇（三三）-----Map总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java提高篇（三三）-----Map总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4588字，纯文字阅读大概需要7分钟。
内容图文
Dictionary：不论什么可将键映射到相应值的类的抽象父类。
眼下被Map接口代替。
TreeMap：有序散列表，实现SortedMap 接口，底层通过红黑树实现。
HashMap：是基于“拉链法”实现的散列表。
底层採用“数组+链表”实现。
WeakHashMap：基于“拉链法”实现的散列表。
HashTable：基于“拉链法”实现的散列表。
总结例如以下：
他们之间的差别：
二、内部哈希： 哈希映射技术
差点儿全部通用Map都使用哈希映射技术。对于我们程序猿来说我们必须要对其有所了解。
哈希映射技术是一种就元素映射到数组的很easy的技术。
因为哈希映射採用的是数组结果，那么必定存在一中用于确定随意键訪问数组的索引机制，该机制可以提供一个小于数组大小的整数。我们将该机制称之为哈希函数。
在Java中我们不必为寻找这种整数而大伤脑筋，因为每一个对象都必定存在一个返回整数值的hashCode方法，而我们须要做的就是将其转换为整数，然后再将该值除以数组大小取余就可以。
例如以下：
int hashValue = Maths.abs(obj.hashCode()) % size;以下是HashMap、HashTable的：
----------HashMap------------
//计算hash值
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//计算key的索引位置
static int indexFor(int h, int length) {
return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length; //确认该key的索引位置
位置的索引就代表了该节点在数组中的位置。下图是哈希映射的基本原理图：
在该图中1-4步骤是找到该元素在数组中位置，5-8步骤是将该元素插入数组中。在插入的过程中会遇到一点点小挫折。在众多肯能存在多个元素他们的hash值是一样的。这样就会得到同样的索引位置，也就说多个元素会映射到同样的位置，这个过程我们称之为“冲突”。
解决冲突的办法就是在索引位置处插入一个链接列表。并简单地将元素加入到此链接列表。当然也不是简单的插入，在HashMap中的处理步骤例如以下：获取索引位置的链表。假设该链表为null，则将该元素直接插入，否则通过比較是否存在与该key同样的key，若存在则覆盖原来key的value并返回旧值，否则将该元素保存在链头（最先保存的元素放在链尾）。以下是HashMap的put方法，该方法具体展示了计算索引位置。将元素插入到适当的位置的全部过程：
public V put(K key, V value) {
//当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap同意为null的原因
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode());
//计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length);
//从i出開始迭代 e,推断是否存在同样的key
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//推断该条链上是否有hash值同样的(key同样)
//若存在同样，则直接覆盖value。返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//改动次数添加1
modCount++;
//将key、value加入至i位置处
addEntry(hash, key, value, i);
return null;
}
HashMap的put方法展示了哈希映射的基本思想，事实上假设我们查看其他的Map。发现其原理都差点儿相同！
三、Map优化
首先我们这样假设，假设哈希映射的内部数组的大小仅仅有1。全部的元素都将映射该位置（0），从而构成一条较长的链表。因为我们更新、訪问都要对这条链表进行线性搜索。这样势必会减少效率。我们假设，假设存在一个很大数组，每一个位置链表处都仅仅有一个元素。在进行訪问时计算其 index 值就会获得该对象，这样做尽管会提高我们搜索的效率，可是它浪费了控件。诚然，尽管这两种方式都是极端的，可是它给我们提供了一种优化思路：使用一个较大的数组让元素可以均匀分布。在Map有两个会影响到其效率，一是容器的初始化大小、二是负载因子。
3.1、调整实现大小
在哈希映射表中。内部数组中的每一个位置称作“存储桶”(bucket)。而可用的存储桶数（即内部数组的大小）称作容量 (capacity)，我们为了使Map对象可以有效地处理随意数的元素，将Map设计成可以调整自身的大小。
我们知道当Map中的元素达到一定量的时候就会调整容器自身的大小，可是这个调整大小的过程其开销是很大的。
调整大小须要将原来全部的元素插入到新数组中。我们知道index = hash(key) % length。
这样可能会导致原先冲突的键不在冲突。不冲突的键如今冲突的。又一次计算、调整、插入的过程开销是很大的，效率也比較低下。
所以，假设我们開始知道Map的预期大小值，将Map调整的足够大，则可以大大减少甚至不须要又一次调整大小，这很有可能会提快速度。
以下是HashMap调整容器大小的过程，通过以下的代码我们可以看到其扩容过程的复杂性：
void resize(int newCapacity) {
Entry[] oldTable = table; //原始容器
int oldCapacity = oldTable.length; //原始容器大小
if (oldCapacity == MAXIMUM_CAPACITY) { //是否超过最大值：1073741824
threshold = Integer.MAX_VALUE;
return;
}
//新的数组：大小为 oldCapacity * 2
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
/*
* 又一次计算阀值 = newCapacity * loadFactor > MAXIMUM_CAPACITY + 1 ?
* newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
*/
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//将元素插入到新数组中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
3.2、负载因子
为了确认何时须要调整Map容器，Map使用了一个额外的參数而且粗略计算存储容器的密度。在Map调整大小之前，使用”负载因子”来指示Map将会承担的“负载量”，也就是它的负载程度，当容器中元素的数量达到了这个“负载量”，则Map将会进行扩容操作。负载因子、容量、Map大小之间的关系例如以下：负载因子 * 容量 > map大小 ----->调整Map大小。
比如：假设负载因子大小为0.75（HashMap的默认值），默认容量为11，则 11 * 0.75 = 8.25 = 8。所以当我们容器中插入第八个元素的时候，Map就会调整大小。
负载因子本身就是在控件和时间之间的折衷。当我使用较小的负载因子时。尽管减少了冲突的可能性。使得单个链表的长度减小了，加快了訪问和更新的速度。可是它占用了很多其他的控件。使得数组中的大部分控件没有得到利用，元素分布比較稀疏，同一时候因为Map频繁的调整大小。可能会减少性能。
可是假设负载因子过大，会使得元素分布比較紧凑，导致产生冲突的可能性加大，从而訪问、更新速度较慢。所以我们一般推荐不更改负载因子的值，採用默认值0.75.
最后
推荐阅读：
java提高篇（二三）—–HashMap
-----原文出自:http://cmsblogs.com/?p=1212,请尊重作者辛勤劳动成果,转载说明出处.
-----个人网站:http://cmsblogs.com
内容总结
以上是互联网集市为您收集整理的Java提高篇（三三）-----Map总结全部内容，希望文章能够帮你解决Java提高篇（三三）-----Map总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。