5.1 哈希表

使用数组设计哈希表的三个要点:

1. 哈希函数: 将 Key 映射为桶中的存储位置
2. 存储桶: 将哈希值相同的元素存储在同一个桶中
3. 哈希冲突: 若桶中元素过多则需要进行扩容, 重新分配元素的位置

5.2.1 问题30: 插入, 删除和随机访问都是*O(1)*的容器

LCR 030. O(1) 时间插入、删除和获取随机元素

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：

• insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
• remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
• getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

示例 :

输入: inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
RandomizedSet randomSet = new RandomizedSet();  // 初始化一个空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入

randomSet.remove(2); // 返回 false，表示集合中不存在 2 

randomSet.insert(2); // 向集合中插入 2 返回 true ，集合现在包含 [1,2] 

randomSet.getRandom(); // getRandom 应随机返回 1 或 2 
  
randomSet.remove(1); // 从集合中移除 1 返回 true 。集合现在包含 [2] 

randomSet.insert(2); // 2 已在集合中，所以返回 false 

randomSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 

提示：

• -231 <= val <= 231 - 1
• 最多进行 2 * 105 次 insert ， remove 和 getRandom 方法调用
• 当调用 getRandom 方法时，集合中至少有一个元素

5.2.1.1 分析

题中要求有两个:

• 插入和删除时间为O(1), 可以使用哈希表实现
• 等概率返回元素, 可以使用数组实现

由于哈希表不能实现等概率返回元素, 那么可以将哈希表和数组相结合来解决:

1. 将元素存储于数组中
2. 构建哈希表(val, index), index 为数组的索引位置
3. 生成(0, n-1)的随机数来返回数组中的元素, 其概率都是相等的

5.2.1.2 题解

type RandomizedSet struct {
    NumsToLoc map[int]int
    Nums      []int
}

/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    return RandomizedSet{
       NumsToLoc: make(map[int]int),
       Nums:      make([]int, 0),
    }
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    if _, ok := this.NumsToLoc[val]; ok {
       return false
    }

    // insert val to the end of 'nums'
    this.NumsToLoc[val] = len(this.Nums)
    this.Nums = append(this.Nums, val)
    return true
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    if _, ok := this.NumsToLoc[val]; !ok {
       return false
    }

    nums := this.Nums
    /** 删除元素 */
    loc := this.NumsToLoc[val]
    // 和最后一个元素交换后删除
    lastEle := nums[len(nums)-1]
    nums[loc] = lastEle
    this.NumsToLoc[lastEle] = loc
    delete(this.NumsToLoc, val)
    this.Nums = nums[:len(nums)-1]

    return true
}

/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
    randIdx := rand.Intn(len(this.Nums))
    return this.Nums[randIdx]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

5.2.2 问题31: 最近最少使用缓存 LRU

LCR 031. LRU 缓存

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

• O(1) 时间复杂度内完成这两种操作

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

5.2.2.1 分析

哈希表的插入和查找时间为O(1), 但是无法获取元素的使用情况.

可将元素按照访问顺序存入链表中, 每次进行操作时, 就将该元素移动至末尾, 那么头节点就自然是使用次数最少的那个元素了.

由于需要删除头节点, 效率最高的是使用双向链表, 只需修改指针指向即可.

流程如下:

1. 构建哈希表(key, node), node 代表一个元素节点
2. 按照访问顺序将元素插入双向链表中
3. 每次进行操作, 将元素移动至表尾
4. 若容量已满, 则删除头节点

5.2.2.2 题解

type LRUCache struct {
    cache    map[int]*ListNode31
    Capacity int
    /* 哨兵节点 */
    head *ListNode31
    tail *ListNode31
}

type ListNode31 struct {
    Key  int
    Val  int
    Prev *ListNode31
    Next *ListNode31
}

func (lru *LRUCache) MoveToTail(node *ListNode31, val int) {
    lru.DeleteNode(node)
    node.Val = val
    lru.InsertToTail(node)
}

func (lru *LRUCache) DeleteNode(node *ListNode31) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (lru *LRUCache) InsertToTail(node *ListNode31) {
    lru.tail.Prev.Next = node
    node.Prev = lru.tail.Prev
    node.Next = lru.tail
    lru.tail.Prev = node
}

func ConstructorLRU(capacity int) LRUCache {
    head := &ListNode31{Key: -1, Val: -1}
    tail := &ListNode31{Key: -1, Val: -1}
    head.Next = tail
    tail.Prev = head

    return LRUCache{
       cache:    make(map[int]*ListNode31, capacity),
       Capacity: capacity,
       head:     head,
       tail:     tail,
    }
}

func (lru *LRUCache) Get(key int) int {
    node, ok := lru.cache[key]
    if !ok {
       return -1
    }
    lru.MoveToTail(node, node.Val) // 移动至表尾
    return node.Val
}

func (lru *LRUCache) Put(key int, value int) {
    if node, ok := lru.cache[key]; ok {
       lru.MoveToTail(node, value)
    } else {
       if len(lru.cache) == lru.Capacity {
          /* 移除头节点 */
          toBeDeleted := lru.head.Next
          lru.DeleteNode(toBeDeleted)
          delete(lru.cache, toBeDeleted.Key)
       }

       newNode := &ListNode31{Key: key, Val: value}
       lru.InsertToTail(newNode)
       lru.cache[key] = newNode
    }
}

Reference

1. 剑指Offer（专项突破版）