哈希表和有序表
# 哈希表和有序表
# 哈希表
- 哈希表在使用层面上可以理解为一种集合结构
- 如果只有key,没有伴随数据value,可以使用HashSet结构
- 如果既有key,又有伴随数据value,可以使用HashMap结构
- 有无伴随数据value,是HashMap和HashSet唯一的区别,实际结构是一样的
- 使用哈希表curd操作(put、remove、put、get),可以认为时间复杂度为O(1),但是常数时间比较大
- 放入哈希表的东西,如果是基础类型,内部按值传递,内存占用是这个基础类型的大小(包括String)
- 放入哈希表的东西,如果不是基础类型,内部按引用传递,内存占用是8字节
# 有序表
- 有序表在使用层面上也可以理解为一种集合结构
- 如果只有key,没有伴随数据value,可以使用TreeSet结构
- 如果既有key,又有伴随数据value,可以使用TreeMap结构
- 有无伴随数据value,是TreeSet和TreeSet唯一的区别,实际结构是一样的
- 与哈希表的区别是,乱序操作之后它是有序的,它有一些额外的api,如firstKey、lastKey、floorKey、ceilingKey等等
- 使用有序表curd(put、remove、put、get)等操作,可以认为时间复杂度为O(logN)
- 放入有序表的东西,如果是基础类型,内部按值传递,内存占用是这个基础类型的大小(包括String)
- 放入有序表的东西,如果不是基础类型,内部按引用传递,内存占用是8字节,排序通过比较器
- 有序表的实现有多种:AVL、SB、红黑树、跳表
上次更新: 5/21/2023, 11:34:33 PM