[Swift]LeetCode706.设计哈希映射|DesignHashMap

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10506126.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。

示例：

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 删除键为2的数据
hashMap.get(2);            // 返回 -1 (未找到)

注意：

所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。

484ms

 1 class MyHashMap {
 2     var arr: [Int]
 3     /** Initialize your data structure here. */
 4     init() {
 5         arr = []
 6     }
 7     
 8     /** value will always be non-negative. */
 9     func put(_ key: Int, _ value: Int) {
10         if arr.count <= key {
11             arr += Array(repeating: -1, count: key-arr.count + 1)
12         }
13         arr[key] = value
14     }
15     
16     /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
17     func get(_ key: Int) -> Int {
18         if key >= arr.count {return -1}
19         return arr[key]
20     }
21     
22     /** Removes the mapping of the specified value key if this map contains a mapping for the key */
23     func remove(_ key: Int) {
24         if key >= arr.count {return}
25         arr[key] = -1
26     }
27 }
28 
29 /**
30  * Your MyHashMap object will be instantiated and called as such:
31  * let obj = MyHashMap()
32  * obj.put(key, value)
33  * let ret_2: Int = obj.get(key)
34  * obj.remove(key)
35  */

492ms

 1 class MyHashMap {
 2 
 3     var array = Array(repeating: -1, count: 1000000)
 4     /** Initialize your data structure here. */
 5     init() {
 6         
 7     }
 8     
 9     /** value will always be non-negative. */
10     func put(_ key: Int, _ value: Int) {
11       array[key] = value
12     }
13     
14     /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
15     func get(_ key: Int) -> Int {
16       return array[key]
17     }
18     
19     /** Removes the mapping of the specified value key if this map contains a mapping for the key */
20     func remove(_ key: Int) {
21       array[key] = -1
22     }
23 }

496ms

 1 class MyHashMap {
 2 
 3     /** Initialize your data structure here. */
 4     typealias Pair = (key: Int, value: Int)
 5     let MAX_LENGTH = 10000
 6     var array: [[Pair]?]
 7     
 8     init() {
 9         array = Array(repeating: nil, count: MAX_LENGTH)
10     }
11     
12     private func getIndex(_ key: Int) -> Int {
13         return key % MAX_LENGTH
14     }
15     
16     private func getPos(_ key: Int, _ bucketIndex: Int) -> Int {
17         if let bucket = array[bucketIndex] {
18             for i in 0..<bucket.count {
19                 let pair = bucket[i]
20                 if pair.key == key {
21                     return i
22                 }
23             }
24         }
25         
26         return -1
27     }
28     
29     /** value will always be non-negative. */
30     func put(_ key: Int, _ value: Int) {
31         let index = getIndex(key)
32         let pos = getPos(key, index)
33         if array[index] != nil {
34             if pos < 0 {
35                 // key not exisiting
36                 array[index]!.append((key,value))
37             } else {
38                 // update key with new value
39                 array[index]![pos] = (key,value)
40             }
41         } else {
42             // create a new bucket
43             array[index] = [(key,value)]
44         }
45     }
46     
47     /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
48     func get(_ key: Int) -> Int {
49         let index = getIndex(key)
50         let pos = getPos(key, index)
51         if array[index] != nil && pos >= 0 {
52             return array[index]![pos].value
53         } 
54         return -1
55     }
56     
57     /** Removes the mapping of the specified value key if this map contains a mapping for the key */
58     func remove(_ key: Int) {
59         let index = getIndex(key)
60         let pos = getPos(key, index) 
61         if array[index] != nil && pos >= 0 {
62             array[index]!.remove(at: pos)
63         }
64     }
65 }

Runtime: 500 ms

Memory Usage: 20.5 MB

 1 class LinkedNode {
 2     var next: LinkedNode?
 3     var key: Int
 4     var val: Int
 5     
 6     init(_ key: Int, _ val: Int) {
 7         self.key = key
 8         self.val = val
 9     }
10 }
11 
12 class MyHashMap {
13     
14     private var nodes: [LinkedNode?]
15 
16     /** Initialize your data structure here. */
17     init() {
18         nodes = Array(repeating: nil, count: 10000)
19     }
20     
21     /** value will always be non-negative. */
22     func put(_ key: Int, _ value: Int) {
23         let index = hash(key)
24         guard let node = nodes[index] else {
25             nodes[index] = LinkedNode(key, value)
26             return
27         }
28         
29         var next: LinkedNode? = node
30         var pre: LinkedNode? = nil
31         while next != nil, next!.key != key {
32             pre = next
33             next = next?.next
34         }
35         
36         if let next = next {
37             next.val = value
38         } else {
39             pre?.next = LinkedNode(key, value)
40         }
41     }
42     
43     /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
44     func get(_ key: Int) -> Int {
45         let index = hash(key)
46         guard let node = nodes[index] else {
47             return -1
48         }
49         
50         var next: LinkedNode? = node
51         var pre: LinkedNode? = nil
52         while next != nil, next!.key != key {
53             pre = next
54             next = next?.next
55         }
56         
57         return next?.val ?? -1
58     }
59     
60     /** Removes the mapping of the specified value key if this map contains a mapping for the key */
61     func remove(_ key: Int) {
62         let index = hash(key)
63         guard let node = nodes[index] else {
64             return
65         }
66         
67         var next: LinkedNode? = node
68         var pre: LinkedNode? = nil
69         while next != nil, next!.key != key {
70             pre = next
71             next = next?.next
72         }
73         
74         if let pre = pre {
75             pre.next = next?.next
76         } else {
77             nodes[index] = next?.next
78         }
79     }
80     
81     private func hash(_ key: Int) -> Int {
82         return key % 10000
83     }
84     
85 }
86 
87 /**
88  * Your MyHashMap object will be instantiated and called as such:
89  * let obj = MyHashMap()
90  * obj.put(key, value)
91  * let ret_2: Int = obj.get(key)
92  * obj.remove(key)
93  */

516ms

 1 class ListNode<T> {
 2     
 3     var value: T
 4     var next: ListNode<T>?
 5     
 6     init(value: T) {
 7         self.value = value
 8     }
 9 }
10 
11 struct KeyValue {
12     var key: Int
13     var value: Int
14 }
15 
16 class MyHashMap {
17     
18     private var buckets = [ListNode<KeyValue>?](repeating: nil, count: 1000)
19 
20     /** Initialize your data structure here. */
21     init() {
22         
23     }
24     
25     /** value will always be non-negative. */
26     func put(_ key: Int, _ value: Int) {
27         if let existingNodes = findNode(key: key) {
28             existingNodes.node.value.value = value
29         } else {
30             let hash = getHash(key)
31             
32             let value = KeyValue(key: key, value: value)
33             let newNode = ListNode<KeyValue>(value: value)
34             newNode.next = buckets[hash % buckets.count]
35             buckets[hash % buckets.count] = newNode
36         }
37     }
38     
39     /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
40     func get(_ key: Int) -> Int {
41         guard let existingNodes = findNode(key: key) else {
42             return -1
43         }
44         return existingNodes.node.value.value
45     }
46     
47     /** Removes the mapping of the specified value key if this map contains a mapping for the key */
48     func remove(_ key: Int) {
49         guard let existingNodes = findNode(key: key) else {
50             return 
51         }
52         
53         if let previous = existingNodes.previous {
54             previous.next = existingNodes.node.next
55         } else {
56             // the key is the head
57             let hash = getHash(key)
58             buckets[hash % buckets.count] = existingNodes.node.next
59         }
60     }
61     
62     private func findNode(key: Int) -> (previous: ListNode<KeyValue>?, node: ListNode<KeyValue>)? {
63         let hash = getHash(key)
64         
65         var previous: ListNode<KeyValue>? = nil
66         var head = buckets[hash % buckets.count]
67         while let _head = head {
68             if _head.value.key == key {
69                 return (previous,_head)
70             }
71             previous = head
72             head = _head.next
73         }
74         
75         return nil // didn't find this key in the bucket
76     }
77     
78     private func getHash(_ key: Int) -> Int {
79         return abs(key.hashValue)
80     }
81 }

528ms

 1 class MyHashMap {
 2 
 3     /** Initialize your data structure here. */
 4     typealias Pair = (key: Int, value: Int)
 5     let MAX_LENGTH = 10000
 6     var array: [[Pair]?]
 7     
 8     init() {
 9         array = Array(repeating: nil, count: MAX_LENGTH)
10     }
11     
12     private func getIndex(_ key: Int) -> Int {
13         return key % MAX_LENGTH
14     }
15     
16     private func getPos(_ key: Int, _ bucketIndex: Int) -> Int {
17         if let bucket = array[bucketIndex] {
18             for i in 0..<bucket.count {
19                 let pair = bucket[i]
20                 if pair.key == key {
21                     return i
22                 }
23             }
24         }
25         
26         return -1
27     }
28     
29     /** value will always be non-negative. */
30     func put(_ key: Int, _ value: Int) {
31         let index = getIndex(key)
32         let pos = getPos(key, index)
33         if array[index] != nil {
34             if pos < 0 {
35                 // key not exisiting
36                 array[index]!.append((key,value))
37             } else {
38                 // update key with new value
39                 array[index]![pos] = (key,value)
40             }
41         } else {
42             // create a new bucket
43             array[index] = [(key,value)]
44         }
45     }
46     
47     /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
48     func get(_ key: Int) -> Int {
49         let index = getIndex(key)
50         let pos = getPos(key, index)
51         if array[index] != nil && pos >= 0 {
52             return array[index]![pos].value
53         } 
54         return -1
55     }
56     
57     /** Removes the mapping of the specified value key if this map contains a mapping for the key */
58     func remove(_ key: Int) {
59         let index = getIndex(key)
60         let pos = getPos(key, index) 
61         if array[index] != nil && pos >= 0 {
62             array[index]!.remove(at: pos)
63         }
64     }
65 }

572ms

  1 class ListNode<T> {
  2     var value: T
  3     var next: ListNode<T>?
  4     
  5     init(value: T) {
  6         self.value = value
  7     }
  8 }
  9 
 10 class HashMap<Key: Hashable, Value> {
 11     
 12     private struct Pair {
 13         var key: Key
 14         var value: Value
 15     }
 16     
 17     private var buckets = [ListNode<Pair>?](repeating: nil, count: 1000)
 18 
 19     func put(key: Key, value: Value) {
 20         
 21         let pair = Pair(key: key, value: value)
 22         
 23         if let existingNodes = find(key: key) {
 24             existingNodes.node.value = pair
 25         } else {
 26             
 27             let index = hash(from: key) % buckets.count
 28             
 29             let newNode = ListNode<Pair>(value: pair)
 30             newNode.next = buckets[index]
 31             buckets[index] = newNode
 32         }
 33     }
 34     
 35     func get(key: Key) -> Value? {
 36         return find(key: key)?.node.value.value
 37     }
 38     
 39     func remove(key: Key) {
 40         guard let nodes = find(key: key) else {
 41             return // couldn't find it
 42         }
 43         
 44         if let previousNode = nodes.previousNode {
 45             previousNode.next = nodes.node.next
 46         } else {
 47             let index = hash(from: key) % buckets.count
 48             buckets[index] = nodes.node.next
 49         }
 50     }
 51     
 52     private func find(key: Key) -> (previousNode: ListNode<Pair>?, node: ListNode<Pair>)? {
 53         let hashValue = hash(from: key)
 54         let index = hashValue % buckets.count
 55         
 56         var previousNode: ListNode<Pair>? = nil
 57         var currentNode: ListNode<Pair>? = buckets[index]
 58         
 59         while let _currentNode = currentNode {
 60             if _currentNode.value.key == key {
 61                 return (previousNode, _currentNode)
 62             }
 63             
 64             previousNode = _currentNode
 65             currentNode = _currentNode.next
 66         }
 67         
 68         return nil
 69     }
 70     
 71     private func hash(from key: Key) -> Int {
 72         return