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

概述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 valu

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 1hashMap.get(3);            // returns -1 (not found)hashMap.put(2,1);          // update the existing valuehashMap.get(2);            // returns 1 hashMap.remove(2);          // remove the mapPing for 2hashMap.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,2);         hashMap.get(1);            // 返回 1hashMap.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] = value14     }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] = -126     }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] = value12     }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] = -122     }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_LENGTH14     }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 i22                 }23             }24         }25         26         return -127     }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 exisiting36                 array[index]!.append((key,value))37             } else {38                 // update key with new value39                 array[index]![pos] = (key,value)40             }41         } else {42             // create a new bucket43             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].value53         } 54         return -155     }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             return27         }28         29         var next: linkednode? = node30         var pre: linkednode? = nil31         while next != nil,next!.key != key {32             pre = next33             next = next?.next34         }35         36         if let next = next {37             next.val = value38         } 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 -148         }49         50         var next: linkednode? = node51         var pre: linkednode? = nil52         while next != nil,next!.key != key {53             pre = next54             next = next?.next55         }56         57         return next?.val ?? -158     }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             return65         }66         67         var next: linkednode? = node68         var pre: linkednode? = nil69         while next != nil,next!.key != key {70             pre = next71             next = next?.next72         }73         74         if let pre = pre {75             pre.next = next?.next76         } else {77             nodes[index] = next?.next78         }79     }80     81     private func hash(_ key: Int) -> Int {82         return key % 1000083     }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: Int13     var value: Int14 }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 = value29         } 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] = newNode36         }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 -143         }44         return existingNodes.node.value.value45     }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.next55         } else {56             // the key is the head57             let hash = getHash(key)58             buckets[hash % buckets.count] = existingNodes.node.next59         }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>? = nil66         var head = buckets[hash % buckets.count]67         while let _head = head {68             if _head.value.key == key {69                 return (prevIoUs,_head)70             }71             prevIoUs = head72             head = _head.next73         }74         75         return nil // dIDn‘t find this key in the bucket76     }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,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 abs(key.hashValue) 73     } 74 } 75  76  77 class MyHashMap { 78      79     private let hashMap = HashMap<Int,Int>() 80  81     /** Initialize your data structure here. */ 82     init() { 83          84     } 85      86     /** value will always be non-negative. */ 87     func put(_ key: Int,_ value: Int) { 88         hashMap.put(key: key,value: value) 89     } 90      91     /** Returns the value to which the specifIEd key is mapped,or -1 if this map contains no mapPing for the key */ 92     func get(_ key: Int) -> Int { 93         guard let value = hashMap.get(key: key) else { 94             return -1 95         } 96         return value 97     } 98      99     /** Removes the mapPing of the specifIEd value key if this map contains a mapPing for the key */100     func remove(_ key: Int) {101         hashMap.remove(key: key)102     }103 }

596ms

  1 struct Pair {  2     let key: Int  3     let value: Int  4 }  5   6 class ListNode<T> {  7       8     var value: T  9      10     var next: ListNode<T>? 11      12     init(value: T) { 13         self.value = value 14     } 15 } 16  17 class MyHashMap { 18      19     private static let bucketLength = 10_000 20      21     private var buckets = [ListNode<Pair>?](repeating: nil,count: MyHashMap.bucketLength) 22  23     /** Initialize your data structure here. */ 24     init() { 25          26     } 27      28     /** value will always be non-negative. */ 29     func put(_ key: Int,_ value: Int) { 30          31         let pair = Pair(key: key,value: value) 32          33         if let nodes = find(key: key) { 34             nodes.node.value = pair // overrIDe the current 35         } else { 36             let hash = hashFromKey(key) 37             let index = hash % buckets.count 38              39             let newNode = ListNode<Pair>(value: pair) 40             newNode.next = buckets[index] 41             buckets[index] = newNode 42         } 43     } 44      45     /** Returns the value to which the specifIEd key is mapped,or -1 if this map contains no mapPing for the key */ 46     func get(_ key: Int) -> Int { 47         guard let nodes = find(key: key) else { 48           return -1 49         } 50         return nodes.node.value.value 51     } 52      53     /** Removes the mapPing of the specifIEd value key if this map contains a mapPing for the key */ 54     func remove(_ key: Int) { 55         guard let nodes = find(key: key) else { 56             return // not node found for the key 57         } 58          59         let node = nodes.node 60          61         if let prevIoUs = nodes.prevIoUs { 62             prevIoUs.next = node.next 63         } else { 64             // its the head 65             let hash = hashFromKey(key) 66             let index = hash % buckets.count  67             buckets[index] = node.next 68         } 69     } 70      71     private func hashFromKey(_ x: Int) -> Int { 72         // var x = x 73         // x = ((x >> 16) ^ x) * 0x45d9f3b; 74         // x = ((x >> 16) ^ x) * 0x45d9f3b; 75         // x = (x >> 16) ^ x; 76         return x*2654435761 77          78 //         if key & 1 == 1 { // odd 79 //             return (key + 1_000_000) 80 //         } else { 81 //             return key * 7 82 //         } 83     } 84      85     private func find(key: Int) -> (prevIoUs: ListNode<Pair>?,node: ListNode<Pair>)? { 86          87         let hash = hashFromKey(key) 88         let index = hash % buckets.count 89          90         var prevIoUsNode: ListNode<Pair>? = nil 91         var currentNode = buckets[index] 92         while let _currentNode = currentNode { 93             if _currentNode.value.key == key { 94                 return (prevIoUsNode,_currentNode) 95             }  96              97             prevIoUsNode = _currentNode 98             currentNode = _currentNode.next // keep searching 99         }        100         101         return nil // dID not find102     }103 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode706. 设计哈希映射 | Design HashMap全部内容，希望文章能够帮你解决[Swift]LeetCode706. 设计哈希映射 | Design HashMap所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。