008.哈希表、有序表和比较器的用法

前置知识：无

提醒：讲解虽然用的 java 语言，但是任何语言都有对等的概念

提醒：后续有专门的章节来详解哈希函数、有序表，这节课就是常规用法展示

哈希表的用法 §

哈希表认为是集合，根据值来做 key 或者根据内存地址做 key

HashSet 和 HashMap 原理一样，有无伴随数据的区别

增、删、改、查时间为 O(1)，但是大常数

所以当 key 的范围是固定的、可控的情况下，可以用数组结构替代哈希表结构：

• 小常数
• 静态结构（临时动态空间 VS. 全局静态空间）

Go 中的哈希表是 map

Java、Go 中哈希表遍历顺序时随机的，每次遍历都可能不一样；JavaScript 中哈希表遍历顺序是添加元素的顺序（高级脚本语言：确实很方便）

注意 §

Java 中通过自定义 hashCode、equals 等方法，可以实现任何类都“根据值做 key”或者“根据内存地址做 key”的需求

但是这里不再展开，因为在算法学习这个范畴内，这些并不重要，还有其他语言的同学也不关心这些

笔试、面试、比赛也都不会用到，课上只说对算法学习重要的内容

这都是 Java 基础：HashMap 底层结构，hashCode、equals 的作用

有序表的用法 §

有序表认为是集合，和哈希表一样，但是有序组织

TreeSet 和 TreeMap 原理一样，有无伴随数据的区别

增、删、改、查、很多和有序相关的操作(floor、ceilling 等)，时间为 O(logn)（底层红黑树）

实际使用上来看有序表的 O(logn) 和哈希表的大常数 O(1) 时间可能是差不了多少的

有序表比较时，相同的东西会去重，如果不想去重就加入更多的比较策略（比较器定制）

要求有序、不要去重：可以使用 堆

有序表在 Java 里就是红黑树实现的，AVL 树、SB 树、替罪羊树、Treap、Splay、跳表等很多结构都可实现同样功能

后续的课程会涉及，这里不做展开，只讲解简单用法

Go 中可以使用第三方包，如：github.com/emirpasic/gods、github.com/iancoleman/orderedmap 等

leetcode 已集成 https://godoc.org/github.com/emirpasic/gods@v1.18.1 第三方库

这道题、这道题 用到了 redblacktree

比较器 §

定制比较策略。用在排序、堆、有序表等很多需要序的结构中都可使用

Java §

Comparable 接口：

public interface Comparable<T> {
	public int compareTo(T o);
}

Compartor 接口：

public interface Comparator<T> {
	public int compare(T o1，T o2);
	boolean equals(Object obj);
}

• 定义类
• Lamda 表达式

返回负数：左边小；返回正数：右边小；返回 0：一样大（相同）

Go §

Less 函数：func(i, j int) bool

sort.Interface 接口：sort.Interface

字符串比较——字典序 §

从左往右依次比较字符的编码大小（如：ASCII 码），一样大（相同）：继续比较下一个字符；不一样大：不往后比了，直接出结果

两个串一直往后比，发现其中一个串没字符了（两个串长度不一样），没字符按最小编码算