java 集合总结-HashMap

HashMap 概述

HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高或将加载因子设置得太低。

需要注意的是：Hashmap 不是同步的，如果多个线程同时访问一个 HashMap，而其中至少一个线程从结构上（指添加或者删除一个或多个映射关系的任何操作）修改了，则必须保持外部同步，以防止对映射进行意外的非同步访问

HashMap 的数据结构

在 Java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是指针（引用），HashMap 就是通过这两个数据结构进行实现。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

 

HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM

 

  fail-fast迭代器备注：

迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。

EXP:

有两个线程（线程A，线程B），其中线程A负责遍历list、线程B修改list。线程A在遍历list过程的某个时候（此时expectedModCount = modCount=N），线程启动，同时线程B增加一个元素，这是modCount的值发生改变（modCount + 1 = N + 1）。线程A继续遍历执行next方法时，通告checkForComodification方法发现expectedModCount  = N  ，而modCount = N + 1，两者不等，这时就抛出ConcurrentModificationException 异常，从而产生fail-fast机制。

以ArrayList为例进一步分析fail-fast产生的原因:

我们知道fail-fast是在操作迭代器时产生的。现在我们来看看ArrayList中迭代器的源代码：

private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount = ArrayList.this.modCount;

        public boolean hasNext() {
            return (this.cursor != ArrayList.this.size);
        }

        public E next() {
            checkForComodification();
            /** 省略此处代码 */
        }

        public void remove() {
            if (this.lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            /** 省略此处代码 */
        }

        final void checkForComodification() {
            if (ArrayList.this.modCount == this.expectedModCount)
                return;
            throw new ConcurrentModificationException();
        }
    }

从上面的源代码我们可以看出，迭代器在调用next()、remove()方法时都是调用checkForComodification()方法，该方法主要就是检测modCount == expectedModCount ? 若不等则抛出ConcurrentModificationException 异常，从而产生fail-fast机制

expectedModCount 是在Itr中定义的：int expectedModCount = ArrayList.this.modCount;所以他的值是不可能会修改的，所以会变的就是modCount。modCount是在 AbstractList 中定义的，为全局变量：

 

protected transient int modCount = 0;
public boolean add(E paramE) {
    ensureCapacityInternal(this.size + 1);
    /** 省略此处代码 */
}

private void ensureCapacityInternal(int paramInt) {
    if (this.elementData == EMPTY_ELEMENTDATA)
        paramInt = Math.max(10, paramInt);
    ensureExplicitCapacity(paramInt);
}

private void ensureExplicitCapacity(int paramInt) {
    this.modCount += 1;    //修改modCount
    /** 省略此处代码 */
}

ublic boolean remove(Object paramObject) {
    int i;
    if (paramObject == null)
        for (i = 0; i < this.size; ++i) {
            if (this.elementData[i] != null)
                continue;
            fastRemove(i);
            return true;
        }
    else
        for (i = 0; i < this.size; ++i) {
            if (!(paramObject.equals(this.elementData[i])))
                continue;
            fastRemove(i);
            return true;
        }
    return false;
}

private void fastRemove(int paramInt) {
    this.modCount += 1;   //修改modCount
    /** 省略此处代码 */
}

public void clear() {
    this.modCount += 1;    //修改modCount
    /** 省略此处代码 */
}

fail-fast解决办法

        方案一：在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，这样就可以解决。但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。

 

        方案二：使用CopyOnWriteArrayList来替换ArrayList。推荐使用该方案。

CopyOnWriteArrayList为何物？ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。 该类产生的开销比较大，但是在两种情况下，它非常适合使用。1：在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。2：当遍历操作的数量大大超过可变操作的数量时。遇到这两种情况使用CopyOnWriteArrayList来替代ArrayList再适合不过了。

private static class COWIterator<E> implements ListIterator<E> {
        /** 省略此处代码 */
        public E next() {
            if (!(hasNext()))
                throw new NoSuchElementException();
            return this.snapshot[(this.cursor++)];
        }

        /** 省略此处代码 */
    }
public boolean add(E paramE) {
        ReentrantLock localReentrantLock = this.lock;
        localReentrantLock.lock();
        try {
            Object[] arrayOfObject1 = getArray();
            int i = arrayOfObject1.length;
            Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1);
            arrayOfObject2[i] = paramE;
            setArray(arrayOfObject2);
            int j = 1;
            return j;
        } finally {
            localReentrantLock.unlock();
        }
    }


    final void setArray(Object[] paramArrayOfObject) {
        this.array = paramArrayOfObject;
    }
CopyOnWriterArrayList的add方法与ArrayList的add方法有一个最大的不同点就在于，下面三句代码：
 
Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1);
arrayOfObject2[i] = paramE;
setArray(arrayOfObject2);

所以CopyOnWriterArrayList所代表的核心概念就是：任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，这样就不会影响COWIterator中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的copy也是相当有损耗的。

 

 

 

归纳

 

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据 equals 方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry 时，也会根据 hash 算法找到其在数组中的存储位置，再根据 equals 方法从该位置上的链表中取出该Entry

 

 

HashMap 的两种遍历方式

第一种

　　Map map = new HashMap();
　　Iterator iter = map.entrySet().iterator();
　　while (iter.hasNext()) {
　　Map.Entry entry = (Map.Entry) iter.next();
　　Object key = entry.getKey();
　　Object val = entry.getValue();
　　}

效率高,以后一定要使用此种方式！

for(Map.Entry<String, Object> entry : paraMap.entrySet())    
{    
    System.out.println(entry.getKey()+": "+entry.getValue());    
} 

其他几种：

循环Map的Key

for(String dataKey : paraMap.keySet())    
{    
    System.out.println(dataKey );               
} 

 

第二种

　　Map map = new HashMap();
　　Iterator iter = map.keySet().iterator();
　　while (iter.hasNext()) {
　　Object key = iter.next();
　　Object val = map.get(key);
　　}

 

效率低,以后尽量少使用！