Hash table

相关概念

  • 哈希表（Hash table），也叫散列表，是根据关键玛值（key value）而直接进行访问的数据结构。
  • 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
  • 这个映射函数叫作散列函数（Hash Function），存放记录的数组叫作哈希表（或散列表）

工程实践

  • 电话号码簿
  • 用户信息表
  • 缓存（LRU Cache）
  • 键值对存储（Redis）

Hash Function

Screen Shot 2020-10-26 at 5.50.23 AM.png

Hash Collisions (哈希碰撞)

Screen Shot 2020-10-26 at 5.51.51 AM.png

  • 退化为链表

时间复杂度

  • 一般来说，哈希表的查询、插入、删除的时间复杂度为 O(1)
  • 最坏情况下，如果哈希表选的不好或 size 太小，容易发生碰撞，此时哈希表退化为链表，时间复杂度为 O(n)

Java code

  • Map：key-value 对，key 不重复

    • new HashMap() / new TreeMap()
    • map.set(key, value)
    • map.get(key)
    • map.has(key)
    • map.size()
    • map.clear()

  • Set：不重复元素的集合

    • new HashSet() / new TreeSet()
    • set.add(value)
    • set.delete(value)
    • set.hash(value)

参考链接

实战题目

参考链接