🍕 简单了解哈希表

哈希表有两种, Map 和 Set, 这两种本质上是一样的。 Map 是 key-value 的形式, Set 是只有 key 的形式。

哈希表的增删改查操作都是 O(1) 级别的。 需要注意的是, 哈希表的常数时间是比较大的, 它相比数组寻址肯定是比较慢一点的。

注意一个概念： 值传递还是引用传递。 通常情况是, 哈希表的规则是:

• 当 key 类型是基础类型时, 哈希表内部是值传递的; 此时哈希表内部会开辟一块空间存储具体的值, 这块空间的大小由具体的值决定。
• 当 key 类型是复杂类型时, 哈希表内部是引用传递时; 此时哈希表内部只会存储引用, 不会重新拷贝一份数据。 引用所占用的空间的大小是固定的。

java 中的哈希表是 HashSet, HashMap 结构 C++ 中的哈希表是 UnorderedSet, UnorderedMap 结构

🍕 简单了解有序表

有序表和哈希表类似, 也有 Map 和 Set 两种。 只不过有序表实现了对 key 进行排序。 所以可以按照特定顺序获取有序表中的 key-value。 注意, 如果传递给有序表的 key 无法直接比较, 则需要传递比较器。

有序表的增删改查操作都是 O(logN) 级别的。

红黑树, AVL 树, size-balance-tree 和跳表等都属于有序表结构。 只是底层具体实现不同。

java 中的有序表是 TreeSet, TreeMap 结构 C++ 中的有序表是 OrderedSet, OrderedMap 结构