散列搜索 & HashMap

搜索算法

包含:顺序搜索、二分搜索、散列搜索。

顺序搜索的性能为 O(N);
二分搜索的性能为 O(logN),但是二分搜索需要集合有序;
散列搜索的性能为 O(1)。

二分搜索

二分搜索涉及到元素的存储结构,包含一般的数组和二叉树。而二叉树又引出了平衡二叉树、红黑二叉树等数据结构。

二叉树结构对于频繁要求集合更新的情况有很大的性能提升。

平衡二叉树的左子树和右子树高度差小于1,避免了单边子树的高度过长,影响搜索性能。

红黑二叉树的左子树和右子树的高度差小于2倍,是为了在平衡二叉树结构对于搜索过程提升的性能和维护该结构的调整消耗间取得平衡。

散列搜索

散列搜索的性能在拥有高效的散列算法时性能为 O(1)。
我这样理解:把散列后形成的集合比作一个把源数据当成下标的数组,搜索性能相当于根据数组下标取数据。

散列搜索的劣势在于无法做到数据的有序性。

HashMap

用 Hash 实现的 Map。

Hash

  1. 合理设计的 Hash 算法可以把源数据均匀地分布到一个固定范围内。
容量超过一定比例后需要扩容。
  2. Hash 冲突可以通过开放地址法和链地址法解决。
Java 采用了链地址法,且在链表长度大于8时会转为红黑树结构。

Map

HashMap: 非线程安全,无序,数组
HashTable: 遗留类,不建议使用
LinkedHashMap: 保留插入顺序的 HashMap
TreeMap: 有序的 Map,红黑树
ConcurrentHashMap: 线程安全的 HashMap

SparseArray/ArrayMap: Android 版的 HashMap,通过双数组实现,适合数据量小的时候用。

参考

  1. Java 8系列之重新认识HashMap
  2. 《算法技术手册》第5章 搜索算法

发表评论