HashMap

1、HashTable和HashMap的区别

HashTable和hashMap底层实现原理一样，都是哈希表数据结构。两者都是基于k-v键值对的数据结构，k不可以相同，v可以相同

两者都是通过数组＋链表 数组是主体，链表是为了解决hash冲突

HashTable的方法都带有synchronized,是线程安全的。

HashTable的key和value都不能为NULL。 HashMap集合的key和value都是可以为null的。

HashTable的初始化容量是11，加载因子是0.75. 容量不要求为2的倍数

HashTable的扩容是：原容量*2+1

HashMap:初始化容量16，官网推荐为2的倍数，为了散列均匀，提交存取效率，默认加载因子0.75

2、介绍

特点

存储形式key value

无序不可重复，key值保障不会重复

初始化容量16，官网推荐为2的倍数，为了散列均匀，提交存取效率，默认加载因子0.75，到75%的时候会扩容，扩容:扩容之后是原容里2倍。0.75是对时间和空间上的一个平衡选择。

key 存储的时候会调用底层hashcode()，hashcode是一串数字，然后会进行取余操作

时间复杂度 每一次取数据O(1) ， 大多数每一次插入数据O(1) ，理论上增删改查都是O(1)

3、Map取值的方式

//通过keySet取出map数据[for-each循环]

//通过EntrySet取出map数据[for-each循环]

//通过EntrySet取出map数据[Iterator遍历]

		//通过keySet取出map数据[for-each循环]
		System.out.println("-------[for-each循环遍历]通过keySet取出map数据-------");
		Set<Integer> keys = map.keySet();   //此行可省略，直接将map.keySet()写在for-each循环的条件中
		for(Integer key:keys){
			System.out.println("key值："+key+" value值："+map.get(key));
		}
		
		//通过EntrySet取出map数据[for-each循环]
		System.out.println("-------[for-each循环遍历]通过EntrySet取出map数据-------");
		Set<Entry<Integer, String>> entrys = map.entrySet();  //此行可省略，直接将map.entrySet()写在for-each循环的条件中
		for(Entry<Integer, String> entry:entrys){
			System.out.println("key值："+entry.getKey()+" value值："+entry.getValue());
		}
		
		//通过EntrySet取出map数据[Iterator遍历]
		System.out.println("-------[Iterator循环遍历]通过EntrySet取出map数据---------");			
		Iterator<Entry<Integer, String>> iterator = map.entrySet().iterator();  //map.entrySet()得到的是set集合，可以																					使用迭代器遍历
		while(iterator.hasNext()){
			Entry<Integer, String> entry = iterator.next();
			System.out.println("key值："+entry.getKey()+" value值："+entry.getValue());
		}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、1.7 1.8区别

• HashMap在1.7中是由 数组＋链表 也可以说 哈希表＋链表 实现的

• HashMap在1.8中是由 数组＋链表 +红黑树

• 在JDK1.7中，HashMap存储的是Entry对象

  在JDK1.8当中，HashMap存储的是实现Entry接口的Node对象

• JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法

  • 为什么从头插法改成尾插法？

    在1.7中，是没有红黑树的 在并发的情况下单链表过长，会成环，发生死循环

    在1.8中，尾插法就可以解决这个问题

• 扩容机制

  • 在JDK1.7的时候是先扩容后插入的，扩容过程中会将原来的数据,放入到新的数组中,但是会重新计算hash值进行分配，这样就会导致无论这一次插入是不是发生hash冲突都需要进行扩容，如果这次插入的并没有发生Hash冲突的话，那么就会造成一次无效扩容，

    但是在1.8的时候是先插入再扩容的，优点是可以减少1.7的一次无效的扩容，因为如果这次插入没有发生Hash冲突的话，那么其实就不会造成扩容

5、写少读多的原理

是一串数字，然后会进行取余操作

key 存储的时候会调用底层hashcode()，hashcode是一串数字，然后会进行取余操作

假定对每个数对8求余，然后放入相应的位置，数据相同会形成一个链表

当链表长度超过8之后，总量超过64，就会变成了红黑树的结构，但是当红黑树的数量有限制，时间复杂度也是O(1)，如果数量没有上限的话，增删改查的时间复杂度从O(1)变成了O(logN)。

当有限制的时候，规定的总量满了或者红黑树满了，就需要扩容。两种扩容机制，总量扩容或者单个扩容

那么如何让增删改查时间复杂度变成O(1)，当数据总量满了之后，对现有的数组进行扩容，然后每个数放入的位置重新进行计算哈希，这样的话进行增删改查的时间复杂度又变成了O(1)。

但是扩容之后重新计算的那一次插入时间复杂度O(n)，大多数还是O(1),平均下来O(logn)，这样虽然降低了增的时间复杂度，但是这样做删改查都做到了时间复杂度O(1),所以一次性写入大量数据，之后不再插入新的数据，只提供查询，这样的增删改查都是O(1)。所以说是写少读多

6、put和get原理

key值不可重复，可以为null，但是只能有一个null

map.put(kv)实现原理:
第-步:先将k，v封装到Node对象当中。
第二步:底层会调用k的hashCode0方法得出hash值，然后通过哈希函数/哈希算法,将hash值转换成数组的下标，下标位置上如果没有任何元素.

就把Node添加到这个位置上了。如果说下标对应的位置上有链表.此时会拿着k和链表上每一个节点中的k进行equals ,如果所有的equals方法返

回都是false。那么这个新节点将会被添加到链表的末尾.如果其中有一个equals返回了tue,就是key值存在，那么这个节点的value将会被覆盖。

如果冲突后，发现该节点是红黑树，就将这个节点挂在树上;

如果冲突后是链表，判断该链表是否大于8，如果大于8并且数组容量小于64，就进行扩容;

如果链表节点大于8并且数组的容量大于64，则将这个结构转换为红黑树;否则，链表插入键值对，若key存在，就覆盖掉value.

map.get(k)实现原理
先调用k的hashCode0方法得出哈号值,通过哈希算法转换成数组下标.通过数组下标快速定位到某个位置上,如果这个位置上什么也没有.返回null,如果这个位置上有单向链表,那么会拿着参数k和单向链表上的每个节点中的k进行equals ,如果所有equals方法返回false。那么get方法返回null .只要其中有一个节点的k和参equal的时候返回true 。那么此时这个节点的value就是我们要找的value . get方法最终返回这个要找的value

7、equals和hashCode

1.向Map集合中存，以及从Map集合中取,都是先调用key的hashCode方法,然后再调用equals方法!
equals方法有可能调用，也有可能不调用。
拿put(k,v)举例,什么时候equals不会调用?
k. hashCode()方法返回哈希值,
哈希值经过哈希算法转换成数組下标。
数组下标位置上如果是null , equals不需要执行。
拿get(k)举例,什么时候equals不会调用?
k. hashCode()方法返回哈希值,
哈希值经过哈希算法转换成数组下标。
数组下标位置上如果是null , equals不需要执行。
2、注意:如果一个类的equals方法重写了,那么hashCode()方法必须重写。
并且equals.方法返回如果是true , hashCode()方法返回的值必须-样。
equals.方法返回true表示两个对象相同,在同一个单向链表上比较。
那么对于同一个单向链表上的节点来说,他们的哈希值都是相同的。
所以hashCode()方法的返回值也应该相同。

**4、终极结论
**放在HashMap集合key 部分的，以及放在HashSet集合中的元素，需要同时重导hashCode方法和equals方法。

同一单向链表的hash相同，因为它们所在的数组下标是一样的，但是同一链表的equals()比较返回false，

8、解决hash冲突的办法有哪些

如果冲突后是链表，判断该链表是否大于8，如果大于8并且数组容量小于64，就进行扩容;

如果链表节点大于8并且数组的容量大于64，则将这个结构转换为红黑树;否则，链表插入键值对，若key存在，就覆盖掉value.

解决Hash冲突方法有:开放定址法、再哈希法、链地址法(拉链法)、建立公共溢出区。 HashMap中采
用的是链地址法。
1、开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次
hash,I p1=H§ ，如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地
址pi。因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次
hash,所以只能在删除的节点上做标记，而不能真正删除节点。
2、再哈希法(双重散列，多重散列)， 提供多个不同的hash函数， 当R1=H1(key1)发生冲突时，再计
算R2=H2(key1)，直到没有冲突为止。这样做虽然不易产生堆集，但增加了计算的时间。

3、链地址法(拉链法)， 将哈希值相同的元素构成一个同义词的单链表并将单链表的头指针存放在哈希
表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除
的情况。

4、建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统-放到溢出

9、为什么在解决hash冲突的时候选择先用链表，再转红黑树?

因为红黑树需要进行左旋,右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于8个的时
候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，红黑树搜索时间复杂度
是O(logn)，而链表是O(n),此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果-开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

10、一般用什 么作为HashMap的key?

一般用Integer、 String 这种不可变类当HashMap当key,而且String最为常用。
●因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就是
HashMap中的键往往都使用字符串的原因。
●因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非
常重要的,这些类已经很规范的重写了hashCode(以及equals()方法。

11、线程安全问题

集合

ArrayList和LinkedList 都是线程不安全的 并发的情况下会发生数据覆盖问题

Vector是线程安全的动态数组
Stack继承自Vector，也是线程安全的 实现一个后进先出的堆栈

HashMap也是线程不安全的 并发的情况下 会发生数据覆盖问题，还会发生死循环，链表成环问题，导致 CPU利用率接近100%；

HashTable是线程安全的

HashTable中对数据进行操作的方法都被synchronized关键字修饰，这种jdk自带的内置锁可以使方法体和代码块一次只能被一个线程执行，**保证了线程安全的问题。 **

因为是锁的整个操作方法，所以在线程竞争激烈的情况下效率非常低下

HashMap为什么线程不安全

●多线程下扩容死循环。

JDK1.7中的HashMap使用头插法插入元素，在多线程的环境下，扩容的时
候有可能导致环形链表的出现，形成死循环。

因此，JDK1.8使用尾插法插入元素，在扩容时会保持
链表元素原本的顺序，不会出现环形链表的问题。
●多线程的put可能导致元素的丢失。多线程同时执行put操作，如果计算出来的索引位置是相同
的，那会造成前一个key被后一个key覆盖，从而导致元素的丢失。此问题在JDK 1.7和JDK1.8中
都存在。
●put和get并发时，可能导致get为null.线程1执行put时，因为元素个数超出threshold而导致
rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和JDK1.8中都存在。

12 ConcurrentHashMap

1.7和1.8

JDK1.7中的ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成，即
ConcurrentHashMap把哈希桶切分成小数组(Segment) ，每个小数组有n个HashEntry组成。
其中，Segment继承了ReentrantLock,所以Segment是一种可重入锁，扮演锁的角色; HashEntry
用于存储键值对数据。

JDK1.8中选择了与HashMap相同的数组+链表+红黑树结构

ConcurrentHashMap是由Synchronized ， CAS 和 Node 实现的，用 Synchronized + CAS 代替 Segment ，这样锁的粒度更小了，也就是说只需要锁住这个链表头结点(红黑树的根节点)，就不会影响其他的哈希桶元素的读写，大大提高了并发度并且不是每次都要加锁了，CAS尝试失败了在加锁。提高了效率。

ConcurrentHashMap和Hashtable的效率哪个更高

ConcurrentHashMap也是线程安全，但效率比HashTable高了很多

ConcurrentHashMap的效率要高于Hashtable,因为Hashtable给整个哈希表加了一把大锁从而实现线
程安全。而ConcurrentHashMap 的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8 中采用CAS+Synchronized实现线程安全。

ConcurrentHashMap的get方法是否要加锁

get方法不需要加锁。因为Node的元素val和指针next是用volatile 修饰的，在多线程环境下线程A
修改结点的val或者新增节点的时候是对线程B可见的。