hello-algo/codes/swift/chapter_hashing/hash_map_chaining.swift
nuomi1 7359a7cb4b
Review Swift codes (#1150)
* feat(swift): review for chapter_computational_complexity

* feat(swift): review for chapter_data_structure

* feat(swift): review for chapter_array_and_linkedlist

* feat(swift): review for chapter_stack_and_queue

* feat(swift): review for chapter_hashing

* feat(swift): review for chapter_tree

* feat(swift): add codes for heap article

* feat(swift): review for chapter_heap

* feat(swift): review for chapter_graph

* feat(swift): review for chapter_searching

* feat(swift): review for chapter_sorting

* feat(swift): review for chapter_divide_and_conquer

* feat(swift): review for chapter_backtracking

* feat(swift): review for chapter_dynamic_programming

* feat(swift): review for chapter_greedy

* feat(swift): review for utils

* feat(swift): update ci tool

* feat(swift): trailing closure

* feat(swift): array init

* feat(swift): map index
2024-03-20 21:15:39 +08:00

138 lines
3.7 KiB
Swift
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: hash_map_chaining.swift
* Created Time: 2023-06-28
* Author: nuomi1 (nuomi1@qq.com)
*/
import utils
/* */
class HashMapChaining {
var size: Int //
var capacity: Int //
var loadThres: Double //
var extendRatio: Int //
var buckets: [[Pair]] //
/* */
init() {
size = 0
capacity = 4
loadThres = 2.0 / 3.0
extendRatio = 2
buckets = Array(repeating: [], count: capacity)
}
/* */
func hashFunc(key: Int) -> Int {
key % capacity
}
/* */
func loadFactor() -> Double {
Double(size) / Double(capacity)
}
/* */
func get(key: Int) -> String? {
let index = hashFunc(key: key)
let bucket = buckets[index]
// key val
for pair in bucket {
if pair.key == key {
return pair.val
}
}
// key nil
return nil
}
/* */
func put(key: Int, val: String) {
//
if loadFactor() > loadThres {
extend()
}
let index = hashFunc(key: key)
let bucket = buckets[index]
// key val
for pair in bucket {
if pair.key == key {
pair.val = val
return
}
}
// key
let pair = Pair(key: key, val: val)
buckets[index].append(pair)
size += 1
}
/* */
func remove(key: Int) {
let index = hashFunc(key: key)
let bucket = buckets[index]
//
for (pairIndex, pair) in bucket.enumerated() {
if pair.key == key {
buckets[index].remove(at: pairIndex)
size -= 1
break
}
}
}
/* */
func extend() {
//
let bucketsTmp = buckets
//
capacity *= extendRatio
buckets = Array(repeating: [], count: capacity)
size = 0
//
for bucket in bucketsTmp {
for pair in bucket {
put(key: pair.key, val: pair.val)
}
}
}
/* */
func print() {
for bucket in buckets {
let res = bucket.map { "\($0.key) -> \($0.val)" }
Swift.print(res)
}
}
}
@main
enum _HashMapChaining {
/* Driver Code */
static func main() {
/* */
let map = HashMapChaining()
/* */
// (key, value)
map.put(key: 12836, val: "小哈")
map.put(key: 15937, val: "小啰")
map.put(key: 16750, val: "小算")
map.put(key: 13276, val: "小法")
map.put(key: 10583, val: "小鸭")
print("\n添加完成后,哈希表为\nKey -> Value")
map.print()
/* */
// key value
let name = map.get(key: 13276)
print("\n输入学号 13276 ,查询到姓名 \(name!)")
/* */
// (key, value)
map.remove(key: 12836)
print("\n删除 12836 后,哈希表为\nKey -> Value")
map.print()
}
}