哈希表和有序表

哈希表

1. 哈希表在使用层面上可以理解为一种集合结构
2. 如果只有key，没有伴随数据value，可以使用HashSet结构
3. 如果既有key，又有伴随数据value，可以使用HashMap结构
4. 有无伴随数据value，是HashMap和HashSet唯一的区别，实际结构是一样的
5. 使用哈希表curd操作（put、remove、put、get），可以认为时间复杂度为O(1)，但是常数时间比较大
6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个基础类型的大小（包括String）
7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节

有序表

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