算法与数据结构-哈希表和有序表哈希表：有序表：

86 阅读 0 评论 57 点赞

我是靠谱客的博主迷你猫咪，最近开发中收集的这篇文章主要介绍算法与数据结构-哈希表和有序表哈希表：有序表：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

哈希表：

（1）哈希表在使用层面可以理解为一种集合结构
（2）如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderSet)
（3）如果既有key，又伴随数据value，可以使用HashMap结构(C++中叫UnOrderMap)
（4）有无伴随数据value，是HashMap和HashSet的唯一区别，底层结构是一样的(HashSet是通过HashMap实现的，只不过Value始终是PRESENT)
（5）哈希表的增/删/改/查可以认为时间复杂度为O(1)，但是常数时间较大
（6）放入哈希表的东西，如果是基础类型，内部按值传递，内存占用为这个东西的大小；如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

有序表：

（1）有序表在使用层面可以理解为一种集合结构
（2）如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderSet)
（3）如果既有key，又伴随数据value，可以使用TreeMap结构(C++中叫OrderMap)
（4）有无伴随数据value，是TreeSet和TreeMap的唯一区别，底层结构是一样的
（5）有序表的增/删/改/查可以认为时间复杂度为O(logN)
（6）红黑树、AVL树、size-balance-tree和跳表都属于有序表结构，只是底层具体实现不同
（7）放入有序表的东西，如果是基础类型，内部按值传递，内存占用为这个东西的大小；如果不是基础类型，必须提供比较器(如下代码所示)，且内部按引用传递，内存占用是这个东西内存地址的大小

Node nodeA = new Node(5);
Node nodeB = new Node(3);
public static class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node o1, Node o2) {
        return o1.value - o2.value;
    }

}
TreeSet<Node> treeSet = new TreeSet<>();
 // 以下的代码会报错，因为没有提供Node类型的比较器
 try {
     treeSet.add(nodeA);
     treeSet.add(nodeB);
 } catch (Exception e) {
     System.out.println("错误信息：" + e.getMessage());
 }

 treeSet = new TreeSet<>(new NodeComparator());
 // 以下的代码没问题，因为提供了Node类型的比较器
 try {
     treeSet.add(nodeA);
     treeSet.add(nodeB);
 } catch (Exception e) {
     System.out.println(e.getMessage());
 }