侯老师语录
六大部件
各类数据结构
1、stack 和 queue 都是在Deque基础上实现的，属于一种适配
2、set也是在map基础上实现的，仅仅用到了map的key【java里 hashset与hashmap区别：hashset靠hashmap实现，只有没有用object，只用key】
3、【这里多提到一个线程安全的概念，java里线程安全的版本是在普通集合的基础上，重新包装每个方法，并加上“Synchronized”关键字实现的】
4、Unordered的 map和set版本基于hash表实现的【java里，bean对象重载hashCode和equals方法可以实现hash表的功能，oc同理】
5、hash表有两种实现方法，侯老师讲的是拉链式
1、拉链式：
将大小为M的数组的每一个元素指向一条链表，链表中的每一个节点都存储一个哈希值为该索引的键，对采用拉链法的哈希实现的查找：首先是根据哈希值找到对应的链表【hashCode】，然后沿着链表顺序找到相应的键【equals】。（使用链接法在最坏的情况下，也就是将所有的key映射到同一个槽中了，这样哈希表就退化成一个链表，这样的话，操作链表的时间复杂度则变成了O(n)，这样哈希表的性能优势就没有了，所以选择一个合适的哈希函数是最为关键的）
2、开放寻址
使用开放寻址法是槽本身直接存放数据，在插入数据时如果key所映射到的索引已经有数据了，这说明发生了冲突，这时会寻找下一个槽，如果该槽也被占用了则继续寻找下一个槽，直到找到没有被占用的槽，在查找时也使用同样的策略来进行。
由于开放寻址法处理冲突的时候占用的是其他槽的位置，这可能导致后续的key在插入的时候更加容易出现哈希冲突，所以采用开放寻址法的哈希表的装载因子不能太高，否则容易出现性能下降。
装载因子是哈希表保存的元素数量和哈希表容量的比，通常采用链接法解决哈希冲突的哈希表的装载因子最好不要大于1，而采用开放寻址法的哈希表最好不要大于0.5.
网友评论