哈希表

有序表与无序表

类型

• C++

  • map通常是红黑树
  • unOrderMap、unOrderSet 则是哈希表（Map是KeyValue对，Set是仅Key）

• Java

  • HashSet、HashMap 哈希表

    常用方法：

    HashMap<Integer, String> mapTest = new HashMap<>();
    // put方法同时作为add和set
    mapTest.put(1, "z");
    mapTest.put(1, "c");
    mapTest.put(2, "2");
    mapTest.remove(2);
    

有序表和哈希表的区别

• 有序表把key按照顺序组织起来，必须提供比较器
• 而哈希表完全不组织，不需要提供比较器
• 哈希表能实现的有序表都能实现，并且有序表还有额外功能

无序表 (哈希表)

哈希表的简单介绍

1. 哈希表在使用层面上可以理解为一种集合结构
2. 伴随数据
   • 如果只有key，没有伴随数据value，可以使用 Java的HashSet结构 (C++的Un0rderedSet)
   • 如果既有key，又有伴随数据value，可以使用 Java的HashMap结构 (C++的UnOrderedMap)
   • 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
3. 性能问题
   • 使用哈希表 增(put)、删(remove)、改(put)、查(get) 的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
4. 内存问题
   • 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
   • 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小
5. 底层实现
   • 有关哈希表的原理，将在提升班“与哈希函数有关的数据结构”一章中讲叙原理
   • 哈希表是有数组和链表组成的

有序表

有序表的简单介绍

1. 有序表在使用层面上可以理解为一种集合结构
2. 伴随数据
   • 如果只有key，没有伴随数据value，可以使用 Java的TreeSet结构 (C++的OrderedSet/Set)
   • 如果既有key，又有伴随数据value，可以使用 Java的TreeMap结构 (C++的OrderedMap/Map)
   • 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
3. 性能问题
   • 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度O(logN)
   • put、remove、containsKey、get、firstKey、floorKey、ceilingKey
4. 内存问题
   • 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
   • 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小
5. 底层实现
   • 下面这些都属于有序表结构，只是底层具体实现不同：
   • 红黑树
   • AVL树
   • size-balance-tree (傻逼树)
   • 跳表等