java集合框架ashMap简单使用以及深度分析

　　public class HashMapextends AbstractMapimplements Map, Cloneable, Serializable基于哈希表的 Map 接口的实现。

　　特点：

　　(1)此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。

　　(除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。)

　　(2)此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

　　(3)此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作(get 和 put)提供稳定的性能。

　　迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。

　　所以，如果迭代性能很重要，则不要将初始容量设置得太高(或将加载因子设置得太低)。

　　HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。

　　(1)容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

　　(2)加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。

　　当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作(即重建内部数据结构)，从而哈希表将具有大约两倍的桶数。

　　通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。

　　加载因子过高虽然减少了空间开销，但同时也增加了查询成本(在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点)。

　　在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。

　　如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

　　如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

　　注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。

　　(结构上的修改是指添加或删除一个或多个映射关系的任何操作;仅改变与实例已经包含的键关联的值不是结构上的修改。)

　　这一般通过对自然封装该映射的对象进行同步操作来完成。

　　如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。

　　最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

　　Map m = Collections.synchronizedMap(new HashMap(...));

　　由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：

　　在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，

　　其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。

　　因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

　　注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。

　　快速失败迭代器尽最大努力抛出 ConcurrentModificationException。

　　因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

　　此类是 java Collections Framework 的成员。

　　(1)

　　containsKey

　　public boolean containsKey(Object key)如果此映射包含对于指定键的映射关系，则返回 true。

　　指定者：

　　接口 Map 中的 containsKey

　　覆盖：

　　类 AbstractMap 中的 containsKey

　　参数：

　　key - 要测试其是否在此映射中存在的键

　　返回：

　　如果此映射包含对于指定键的映射关系，则返回 true。

　　(2)

　　keySet

　　public Set keySet()返回此映射中所包含的键的 Set 视图。该 set 受映射的支持，所以对映射的更改将反映在该 set 中，反之亦然。如果在对 set 进行迭代的同时修改了映射(通过迭代器自己的 remove 操作除外)，则迭代结果是不确定的。该 set 支持元素的移除，通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。

　　指定者：

　　接口 Map 中的 keySet

　　覆盖：

　　类 AbstractMap 中的 keySet

　　返回：

　　此映射中包含的键的 set 视图【有关 set 使用 见下文。】

　　下面借鉴一个实例演示解析：

　　public class HashMapTest {

　　public static void main(String[] args) {

　　HashMap keySetMap = new HashMap();

　　HashMap entrySetMap=new HashMap();

　　for (int i= 0;i<1000;i++) {

　　keySetMap.put(""+i, "keySet");

　　}

　　for(int i=0;i<1000;i++){

　　entrySetMap.put(""+i,"entrySet");

　　}

　　long startTimeOne = System.currentTimeMillis();

　　Iterator keySetIterator = keySetMap.keySet().iterator();

　　while (keySetIterator.hasNext()) {

　　System.out.println(keySetMap.get(keySetIterator.next()));

　　}

　　System.out.println("keyset遍历时间-------------------------------:"+(System.currentTimeMillis()-startTimeOne));

　　long startTimeTwo=System.currentTimeMillis();

　　Iterator> entrySetIterator=entrySetMap.entrySet().iterator();

　　while(entrySetIterator.hasNext()){

　　Entry entry=entrySetIterator.next();

　　System.out.println(entry.getValue());

　　}

　　System.out.println("entryset遍历时间---------------------------:"+(System.currentTimeMillis()-startTimeTwo));

　　}

　　}

　　通过多次运行测试发现，entryset遍历时间比keyset遍历时间短许多，entryset方式的性能通常要比keyset方式高一倍。

　　三。原因何在?

　　通过查看源代码发现，调用keySetMap.keySet()这个方法会生成keyIterator迭代器，

　　其next()方法只返回其key值，然后再通过key值在keySetMap中获得其value值，代码如：keySetMap.get(keySetIterator.next())

　　而调用entrySetMap.entrySet()方法会生成EntryIterator迭代器，其next()方法返回一个Entry对象的一个实例，其中包含key值和value值。

　　如果遍历HashMap时只取其key值，那么两种方式的遍历在性能上应该是相同的。

　　但同时取key值和value值时，keyset方式比entryset方式多遍历了一次table，此时keyset方式性能差些。

　　hashMap深度分析(转载)

　　java.util.HashMap是很常见的类，前段时间公司系统由于对HashMap使用不当，导致cpu百分之百，

　　在并发环境下使用HashMap 而没有做同步，可能会引起死循环，关于这一点，sun的官方网站上已有阐述，这并非是bug。

　　HashMap的数据结构

　　HashMap主要是用数组来存储数据的，我们都知道它会对key进行哈希运算，哈系运算会有重复的哈希值，对于哈希值的冲突，HashMap采用链表来解决的。

　　在HashMap里有这样的一句属性声明：

　　transient Entry[] table;

　　Entry就是HashMap存储数据所用的类，它拥有的属性如下

　　final K key;

　　V value;

　　final int hash;

　　Entry next;

　　看到next了吗?next就是为了哈希冲突而存在的。比如通过哈希运算，一个新元素应该在数组的第10个位置，但是第10个位置已经有Entry，那么好吧，将新加的元素也放到第10个位置，将第10个位置的原有Entry赋值给当前新加的 Entry的next属性。数组存储的是链表，链表是为了解决哈希冲突的，这一点要注意。

　　几个关键的属性

　　存储数据的数组

　　transient Entry[] table; 这个上面已经讲到了

　　默认容量

　　static final int DEFAULT_INITIAL_CAPACITY = 16;

　　最大容量

　　static final int MAXIMUM_CAPACITY = 1 << 30;

　　默认加载因子，加载因子是一个比例，当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容

　　static final float DEFAULT_LOAD_FACTOR = 0.75f;

　　当实际数据大小超过threshold时，HashMap会将容量扩容，threshold=容量*加载因子

　　int threshold;

　　加载因子

　　final float loadFactor;

　　HashMap的初始过程

　　构造函数1：

　　public HashMap(int initialCapacity, float loadFactor) {

　　if (initialCapacity < 0)

　　throw new IllegalArgumentException("Illegal initial capacity: " +

　　initialCapacity);

　　if (initialCapacity > MAXIMUM_CAPACITY)

　　initialCapacity = MAXIMUM_CAPACITY;

　　if (loadFactor <= 0 || Float.isNaN(loadFactor))

　　throw new IllegalArgumentException("Illegal load factor: " +

　　loadFactor);

　　// Find a power of 2 >= initialCapacity

　　int capacity = 1;

　　while (capacity < initialCapacity)

　　capacity <<= 1;

　　this.loadFactor = loadFactor;

　　threshold = (int)(capacity * loadFactor);

　　table = new Entry[capacity];

　　init();

　　}

　　重点注意这里

　　while (capacity < initialCapacity)

　　capacity <<= 1;

　　capacity才是初始容量，而不是initialCapacity，这个要特别注意，如果执行new HashMap(9,0.75);

　　那么HashMap的初始容量是16，而不是9，想想为什么吧。

　　构造函数2

　　public HashMap(int initialCapacity) {

　　this(initialCapacity, DEFAULT_LOAD_FACTOR);

　　}

　　构造函数3，全部都是默认值

　　public HashMap() {

　　this.loadFactor = DEFAULT_LOAD_FACTOR;

　　threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

　　table = new Entry[DEFAULT_INITIAL_CAPACITY];

　　init();

　　}

　　构造函数4:

　　public HashMap(Map m) {

　　this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

　　DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

　　putAllForCreate(m);

　　}

　　如何哈希

　　HashMap并不是直接将对象的hashcode作为哈希值的，

　　而是要把key的hashcode作一些运算以得到最终的哈希值，

　　并且得到的哈希值也不是在数组中的位置哦，无论是get还是put还是别的方法，计算哈希值都是这一句：

　　int hash = hash(key.hashCode());

　　hash函数如下：

　　static int hash(int h) {

　　return useNewHash ? newHash(h) : oldHash(h);

　　}

　　useNewHash声明如下：

　　private static final boolean useNewHash;

　　static { useNewHash = false; }

　　这说明useNewHash其实一直为false且不可改变的，hash函数里对 useNewHash的判断真是多余的。

　　private static int oldHash(int h) {

　　h += ~(h << 9);

　　h ^= (h >>> 14);

　　h += (h << 4);

　　h ^= (h >>> 10);

　　return h;

　　}

　　private static int newHash(int h) {

　　// This function ensures that hashCodes that differ only by

　　// constant multiples at each bit position have a bounded

　　// number of collisions (approximately 8 at default load factor).

　　h ^= (h >>> 20) ^ (h >>> 12);

　　return h ^ (h >>> 7) ^ (h >>> 4);

　　}

　　其实HashMap的哈希函数会一直都是oldHash。

　　如果确定数据的位置

　　看下面两行

　　int hash = hash(k.hashCode());

　　int i = indexFor(hash, table.length);

　　第一行，上面讲过了，是得到哈希值，

　　第二行，则是根据哈希指计算元素在数组中的位置了，位置的计算是将哈希值和数组长度按位与运算。

　　static int indexFor(int h, int length) {

　　return h & (length-1);

　　}

　　put方法到底作了什么?

　　public V put(K key, V value) {

　　if (key == null)

　　return putForNullKey(value);

　　int hash = hash(key.hashCode());

　　int i = indexFor(hash, table.length);

　　for (Entry 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;

　　}

　　如果key为NULL，则是单独处理的，看看putForNullKey方法：

　　private V putForNullKey(V value) {

　　int hash = hash(NULL_KEY.hashCode());

　　int i = indexFor(hash, table.length);

　　for (Entry e = table[i]; e != null; e = e.next) {

　　if (e.key == NULL_KEY) {

　　V oldValue = e.value;

　　e.value = value;

　　e.recordAccess(this);

　　return oldValue;

　　modCount++;

　　addEntry(hash, (K) NULL_KEY, value, i);

　　return null;

　　}

　　NULL_KEY的声明：static final Object NULL_KEY = new Object();

　　这一段代码是处理哈希冲突的，就是说，在数组某个位置的对象可能并不是唯一的，它是一个链表结构.

　　根据哈希值找到链表后，还要对链表遍历，找出key相等的对象，替换它，并且返回旧的值。

　　for (Entry e = table[i]; e != null; e = e.next) {

　　if (e.key == NULL_KEY) {

　　V oldValue = e.value;

　　e.value = value;

　　e.recordAccess(this);

　　return oldValue;

　　}

　　}

　　如果遍历完了该位置的链表都没有找到有key相等的，那么将当前对象增加到链表里面去

　　modCount++;

　　addEntry(hash, (K) NULL_KEY, value, i);

　　return null;

　　且看看addEntry方法:

　　void addEntry(int hash, K key, V value, int bucketIndex) {

　　Entry e = table[bucketIndex];

　　table[bucketIndex] = new Entry(hash, key, value, e);

　　if (size++ >= threshold)

　　resize(2 * table.length);

　　}

　　table[bucketIndex] = new Entry(hash, key, value, e);

　　新建一个Entry对象，并放在当前位置的Entry链表的头部，看看下面的 Entry构造函数就知道了，注意红色部分。

　　Entry(int h, K k, V v, Entry n) {

　　value = v;

　　next = n;

　　key = k;

　　hash = h;

　　}

　　如何扩容?

　　当put一个元素时，如果达到了容量限制，HashMap就会扩容，新的容量永远是原来的2倍。

　　上面的put方法里有这样的一段：

　　if (size++ >= threshold)

　　resize(2 * table.length);

　　这是扩容判断，要注意，并不是数据尺寸达到HashMap的最大容量时才扩容.

　　而是达到 threshold指定的值时就开始扩容， threshold=最大容量*加载因子。

　　看看resize方法:

　　void resize(int newCapacity) {

　　Entry[] oldTable = table;

　　int oldCapacity = oldTable.length;

　　if (oldCapacity == MAXIMUM_CAPACITY) {

　　threshold = Integer.MAX_VALUE;

　　return;

　　}

　　Entry[] newTable = new Entry[newCapacity];

　　transfer(newTable);

　　table = newTable;

　　threshold = (int)(newCapacity * loadFactor);

　　}

　　重点看看红色部分的 transfer方法:

　　void transfer(Entry[] newTable) {

　　Entry[] src = table;

　　int newCapacity = newTable.length;

　　for (int j = 0; j < src.length; j++) {

　　Entry e = src[j];

　　if (e != null) {

　　src[j] = null;

　　do {

　　Entry next = e.next;

　　int i = indexFor(e.hash, newCapacity);

　　e.next = newTable[i];

　　newTable[i] = e;

　　e = next;

　　} while (e != null);

　　}

　　tranfer方法将所有的元素重新哈希，因为新的容量变大，所以每个元素的哈希值和位置都是不一样的。

　　正确的使用HashMap

　　1：不要在并发场景中使用HashMap

　　HashMap是线程不安全的，如果被多个线程共享的操作，将会引发不可预知的问题，

　　据sun的说法，在扩容时，会引起链表的闭环，在get元素时，就会无限循环，后果是cpu100%。

　　看看get方法的红色部分

　　public V get(Object key) {

　　if (key == null)

　　return getForNullKey();

　　int hash = hash(key.hashCode());

　　for (Entry e = table[indexFor(hash, table.length)];

　　e != null;

　　e = e.next) {

　　Object k;

　　if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

　　return e.value;

　　return null;

　　2：如果数据大小是固定的，那么最好给HashMap设定一个合理的容量值

　　根据上面的分析，HashMap的初始默认容量是16，默认加载因子是0.75.

　　也就是说，如果采用HashMap的默认构造函数,

　　当增加数据时，数据实际容量超过10*0.75=12时，HashMap就扩容，扩容带来一系列的运算.新建一个是原来容量2倍的数组，对原有元素全部重新哈希，如果你的数据有几千几万个，而用默认的HashMap构造函数，那结果是非常悲剧的，因为HashMap不断扩容，不断哈希，在使用HashMap的场景里，不会是多个线程共享一个HashMap,除非对HashMap包装并同步,由此产生的内存开销和cpu开销在某些情况下可能是致命的