哈希表
2019-02-14 本文已影响1人
952625a28d0d
映射（Map） 和 集合（Set）
-
哈希表（HashTable）、哈希函数（Hash Function）、哈希碰撞（Collisions）
-
Map & Set
-
HashMap、HashSet、TreeMap、TreeSet
-
HashTable
image.png
-
Coliisions
image.png
image.png
- Set实现是用树或者二叉树，查找起来比List的效率要高。
image.png
-
HashMap、HashSet 实现是用数组、链表形式，而TreeMap、TreeSet实现是用二叉树的形式。那么HashMap的查找的时间复杂度是O(1)，而TreeMap查找的时间复杂度是log n的时间复杂度
-
前者是乱序排列，后者是有序排列。
-
如果对时间复杂度要求很高的情况下，尽量使用HashMap或者HashSet，但如果要求使用一种相对有序的方式来储存的情况下，就要使用TreeMap或者TreeSet。
最佳实践
image.png
最后贴上不同数据结构的时间复杂度
image.png
