Map和Set

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。数据的一般查找方式有两种：直接遍历和二分查找。但这两种查找方式都有很大的局限性，也不便于对数据进行增删查改等操作。对于这一类数据的查找，Map和Set显然是个好的选择。

Map中存储的是键值对（key和value），即每一个key都有一个对应的value值，多个key可以有同一个value，但key只能有一个。Set中只存储键（key）。

Set即数学上的集合，继承于Collection接口；Map则属于一个单独的接口。

Java中实现Set接口的常用类有TreeSet和HashSet；实现Map接口的常用类有TreeMap和HashMap。

TreeMap底层是一颗红黑树（近似平衡的二叉搜索树），搜索或修改数据的时间复杂度为O（log2N）。TreeMap存储的数据为关于Key有序的，搜索或修改数据也通过比较实现。

HashMap底层是哈希桶，获取或者操作数据的时间复杂度为O（1）。其存储的数据无序。

TreeMap的key不可以为null，HashMap的key和value都有可以为null。

TreeSet和HashSet与上述相同，其底层通过TreeMap和HashMap实现。

由于TreeMap的时间复杂度高于HashMap，只要不要求有序，一般都使用HashMap。HashMap的存储方式其实是通过某个函数得出的值直接存放在Hash表中相应地址处。搜索时通过相同的函数拿到相应数据。

哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)。

不管怎么设计哈希函数，总有可能有两个不一样的值计算得出相同的地址。这时就引起了哈希冲突。冲突是必然的，但应尽可能地减少冲突。

冲突较多可能是由于hash函数的设计不合理造成的，因此设计哈希函数是应该遵循一定的规则：

• 定义域必须包括所有需要存放的值
• 存放的地址空间应该尽可能均匀
• 哈希函数应该比较简单

常见hash函数有：直接定制法、除留余数法、平方取中法、随机数法、数学分析法等。其中直接定制法(Hash(key) = A * key + B)和除留余数法(Hash(key) = key % p(p < m)，m为分配的空间大小)比较常用。key可以通过hashCode()函数计算得出。

当然，Hash函数设计的再巧妙，也无法避免冲突。当冲突率很高时，需要降低负载因子，负载因子定义为：填入表中的元素 / 哈希表长度。

因此降低冲突的做法应为增加数组的长度。

为了解决冲突问题，可以采用开放定址法。即当发生冲突时，如果哈希表未满，则放到下一个地址并存放。具体做法为线性探测法和二次探测法：

线性探测即当发生冲突时，就存放在冲突位置的下一个地址（如果也冲突就继续后放）。但这样会造成数据集中在某一片区域。此时可以采用二次探测，当发生冲突时，找下一个空位置的方法为：Hi = (H0 + i^2) % m。

除此之外可以采用链地址法，即哈希桶。把所有产生冲突的数据放在一个子集中，称为一个桶，各个数据通过链表连接。当冲突严重时，子集中数据较多，也可以把子集转换为哈希表或搜索树。

在Java中，当冲突严重时，HashSet和HashMap中的链表会转换成红黑树。

key虽然可以通过hashCode()计算得出，但不同的key有可能得到相同的hashCode，因此要确定key值是否相同还需要通过equals判断。

如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，则必须覆写 hashCode 和 equals 方

法，而且要做到 equals 相等的对象，hashCode 一定是一致的。即：