Java笔记------HashSet原理详解以及HashMap

Set数据结构是我们在开发中经常用到的，其存储思想其实和HashMap很类似。今天记录一下Set的详细知识。

（一）Set接口有两个实现类，一个是HashSet，另外一个是LinkedHashSet。HashSet是无序的，LinkedHashSet是有序的。

（二）在JDK1.8之前，HashSet的底层是由数组+链表==》（哈希表），在JDK1.8及其之后，HashSet的底层是由数组+链表 或者数组+红黑树，在哈希值相同，存储的数据不超过8个的时候，是采用数组+链表，哈希值相同，超过8个数据的时候，就会采用数组+红黑树。
如下图：假设中文字符串：测试、你好、大哥的哈希值相同。字符串11、22、33、44、55、66、77的哈希值相同。当相同哈希值的数据超过或者等于8时，就会采用红黑树，因为采用红黑树，查询的速度时很快的。

（三）HashSet是如何存储数据的呢？
（1）当存储数据的时候，会先调用该数据的hasCode()方法，获取哈希值。根据相同的哈希值，把数据存入对应的链表，然后调用该链表中的数据的equals()方法，判断该数据内容是否相同和已经存储的数据内容相同。如果内容不同，则存储。
我们用下图举例： 当存储 “测试” 的时候，会先调用该数据的hasCode方法获取哈希值，然后把该数据存进对应的链表。由于存入的是第一个数据，该哈希值没有其他数据，所以之前存储。
当存储第二个数据 ”你好“ 的时候，也会调用该数据的hasCode()获取哈希值，然后存在对应的链表中，这个时候，该链表就有两个数据了，就会产生哈希冲突，然后就会调用 ：测试.equals(你好)，判断他们的值是否相同,不同，测存储。

（四）LinkedHashSet 无非就是 哈希表+链表。多了一条链表用于记录数据的顺序。其存储原理和HashSet一摸一样，我就不多说了。

（五）这里多记录一下，其实HashSet和HashMap的储存思想大致相同，都是采用哈希表（数据+链表 或者 数据+红黑树）， 无非是多了一个Entry内部类，用于记录key，value。每一对key，value都有一个Entry相对应。Entry相当于人们的结婚证，上面记录了男方 和女方，也就是key和value。所以可以通过Entry直接获取到key和value。
重点：通过自己的测试，HashMap 使用entry来获取Map里面的数据的速度，是用过增强for循环方式的2倍多。所以在遍历HashMap的时候，最好使用entry来遍历。