java集合：HashSet和HashMap简述

java集合：HashSet和HashMap简述

HashSet底层实际上是一个HashMap

HashSet的特点是无序、不可重复。
而HashMap中的key也是无序不可重复的。
因此可以理解为“HashSet就相当于HashMap中的Key部分。HashSet有什么特点，HashMap中的Key就有什么特点。

HashMap底层就是一个哈希表/散列表

哈希表是数组和单向链表的结合：
数组查询效率高，但是增删效率低。
单向链表查询效率低，但是增删效率高。
因此为了两者兼得，所以设计了哈希表，在查询效率和增删效率方面均能达到均衡。

哈希表本质是一个数组，只不过这个数组中的每一个元素又是单向链表。
final int hash;这个是哈希值，是通过key调用hashCode方法，通过哈希算法得出的值。

不同的单向链表与单向链表之间哈希值是不一样的，但是同一个单向链表中每一个节点的哈希值是相同的，代表的是数组的下标，哈希值和数组下标之间是有相对应的散列函数换算规则。

HashMap中有一个方法：Object get(Object key)

底层是调用key的hashCode()方法，得到对应的哈希值，就得到了数组中类似的“下标”,然后通过这个“下标”来定位这个单向链表，然后再遍历单向链表的元素的key值，就能找到相对应的元素。

HashMap中有一个存储元素的方法：void put(Object key, Object value);

添加的元素是往现有的单向链表上加还是在新的数组位置上加？

①肯定会先对传入的key先调用hashCode方法，得到哈希值;
②再通过哈希值equals比对：

A.如果与某一单向链表的哈希值相等，再进行下一步。拿着传入的key进行equals比对，如果该单向链表中已存在所有元素的key值与该key值都不相等，则将传入value加到相应的单向列表中；如果发现单向链表用某一元素key值与传入key值相等，由于key值不可重复，放弃添加该value元素。

B.如果该哈希值是一个新的值，则会在数组新的位置上存储，并创建新的单向链表。