HashMap相关知识点

HashMap:

1、HashMap基本概念

HashMap是储存键值对的数据储存结构，其底层实际是数组加链表的形式。一个key对应多个value，key和value也可以是null值，相对比的是Hashtable，不可以是null值；HashMap是线程不安全的，对比的是Hashtable，是线程安全的；

2、HashMap的工作原理（储存步骤）

HashMap是无序不可重复的，当存入一个key1-value1值时。会先计算key1的hashCode方法，计算其Hash值，再根据Hash值，确定一个底层数组table[]的下标i，此处要明确table[3]其实是一个链表的头结点，即索引；比如i=3;则会判断table[3]是否为空（key1不为null的时候），如果table[3]为空，则存入;如果table[3]不为空，则表示key1和已有的键值发生了hash冲突；则将key1-value1，entry对存入以table[3]为头结点的链表中。

另外对于两个hashcode值一样的Key如何比较取出值呢？先根据key值找到数组的位置下标，然后用调用key.equals和链表的挨个比较，找到一样的值取出；

PS：Hash冲突并不代表两个对象就一样了，两个对象一样hash值一定一样，但是hash值一样并不代表对象一样；另外使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择

3、HashMap扩容

HashMap 中两个重要的参数：“初始容量” 和 “加载因子”(load factor)；容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度（默认0.75）。　当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构，桶数Ｘ２）。加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少, 好处是:冲突的机会减小了,但:空间浪费多了。

4、HashMap-fast-fail问题

String[] stringArray = {"a","b","c","d"};
List<String> strings = Arrays.asList(stringArray);
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()) {    
  if(iterator.next().equals("c")) {        
    strings.remove("c");    
  }
}
或者
for(String s : strings) {    
  if(s.equals("c")) {        
strings.remove("c");
  }
}
都会报错：ConcurrentModificationException，原因是在使用迭代器时候底层数据被修改，最常见于数据源不是线程安全的类

所以在遍历的时候是不能进行数据操作的；这种fast-fail机制也不能在并行开发的时候一定发现问题，所以并不能用来提示保证没有多线程在同时操作非线程安全的数据；当然对于List接口有例外：

ListIterator listIterator = list.listIterator();  
    while (listIterator.hasNext()) {  
        Object object = (Object) listIterator.next();  
        if (object.equals("3")) {  
            listIterator.add("a");  
        }else {  
            System.out.println(listIterator.next());  
        }  
    }  

5、HashMap和CurrentHashMap

ConcurrentHashMap是在hashMap的基础上，将数据分为多个segment(类似hashtable)，默认16个（concurrency level），然后在每一个分段上都用锁进行保护，从而让锁的粒度更精细一些，并发性能更好。同步的集合类（Hashtable和Vector），同步的封装类（使用Collections.synchronizedMap()方法和Collections.synchronizedList()方法返回的对象）可以创建出线程安全的Map和List。但是有些因素使得它们不适合高并发的系统。它们仅有单个锁，对整个集合加锁，以及为了防止ConcurrentModificationException异常经常要在迭代的时候要将集合锁定一段时间，这些特性对可扩展性来说都是障碍。ConcurrentHashMap和CopyOnWriteArrayList保留了线程安全的同时，也提供了更高的并发性。ConcurrentHashMap和CopyOnWriteArrayList并不是处处都需要用，大部分时候你只需要用到HashMap和ArrayList，它们用于应对一些普通的情况。