中国文明网联盟网站建设,嘉兴网站建设全包,青岛专业制作网站,黄页引流推广网站Map和set是一种专门用来进行搜索的容器或者数据结构#xff0c;其搜索的效率与其具体的实例化子类有关。数据的一般查找方式有两种#xff1a;直接遍历和二分查找。但这两种查找方式都有很大的局限性#xff0c;也不便于对数据进行增删查改等操作。对于这一类数据的查找其搜索的效率与其具体的实例化子类有关。数据的一般查找方式有两种直接遍历和二分查找。但这两种查找方式都有很大的局限性也不便于对数据进行增删查改等操作。对于这一类数据的查找Map和Set显然是个好的选择。
Map中存储的是键值对key和value即每一个key都有一个对应的value值多个key可以有同一个value但key只能有一个。Set中只存储键key。
Set即数学上的集合继承于Collection接口Map则属于一个单独的接口。
Java中实现Set接口的常用类有TreeSet和HashSet实现Map接口的常用类有TreeMap和HashMap。
TreeMap底层是一颗红黑树近似平衡的二叉搜索树搜索或修改数据的时间复杂度为Olog2N。TreeMap存储的数据为关于Key有序的搜索或修改数据也通过比较实现。
HashMap底层是哈希桶获取或者操作数据的时间复杂度为O1。其存储的数据无序。
TreeMap的key不可以为nullHashMap的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 一定是一致的。即
