数据结构与算法笔记(4)映射和集合

映射,集合(Map,Set)

哈希表&哈希函数(HashTable&Hash Function)

哈希函数
数据结构与算法笔记(4)映射和集合
通过函数将某一元素放在数组的某个位置

哈希碰撞(Hash Collisions):数组里某个位置有两个元素
数据结构与算法笔记(4)映射和集合
解决哈希碰撞的方法,可以用拉链法,即将该位置用链表放置。

List vs Map vs Set

数据结构与算法笔记(4)映射和集合

HashMap vs TreeMap

HashSet vs TreeSet

HashTable vs Binary-Search-Tree

左边用hash表存储,右边用二叉树来存
左边查找时O(1)复杂度,右边查找时间复杂度为O(log N)
左边相对无序,右边相对有序
数据结构与算法笔记(4)映射和集合
数据结构与算法笔记(4)映射和集合