Created
June 17, 2021 06:45
-
-
Save conf8o/bd06290070308d45add81cce08d46625 to your computer and use it in GitHub Desktop.
ハッシュテーブルの実装
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
protocol Potato { | |
func hash() -> Int | |
} | |
extension Potato where Self: Hashable { | |
func hash() -> Int { | |
return self.hashValue | |
} | |
} | |
enum Imozuru<Imo> { | |
indirect case tsuru(Imo, Imozuru<Imo>) | |
case null | |
} | |
extension Imozuru: Sequence { | |
func makeIterator() -> ImozuruIterator<Imo> { | |
return ImozuruIterator(imozuru: self) | |
} | |
} | |
struct ImozuruIterator<Imo>: IteratorProtocol { | |
var imozuru: Imozuru<Imo> | |
mutating func next() -> Imo? { | |
guard case let .tsuru(imo, rest) = imozuru else { | |
return nil | |
} | |
imozuru = rest | |
return imo | |
} | |
} | |
extension Imozuru: CustomStringConvertible { | |
var description: String { | |
var s = "" | |
for imo in self { | |
s.append("\(imo)~") | |
} | |
return s + "*" | |
} | |
} | |
struct HashedPotatoField<Key: Potato, Imo> { | |
var imozuruField: [Imozuru<(key: Key, imo: Imo)>] | |
var fieldSize: Int | |
init() { | |
self.init(fieldSize: 16) | |
} | |
init(fieldSize: Int) { | |
self.fieldSize = fieldSize | |
imozuruField = Array(repeating: .null, count: fieldSize) | |
} | |
subscript(potato: Key) -> Imo? { | |
get { | |
let index = abs(potato.hash()) % fieldSize | |
let tsuru = imozuruField[index] | |
return tsuru.first { $0.key.hash() == potato.hash() }?.imo | |
} | |
set(imo) { | |
let index = abs(potato.hash()) % fieldSize | |
let tsuru = imozuruField[index] | |
imozuruField[index] = .tsuru((key: potato, imo: imo!), tsuru) | |
} | |
} | |
} | |
let tsuru: Imozuru = .tsuru("あ", | |
.tsuru("い", | |
.tsuru("う", | |
.tsuru("え", | |
.null)))) | |
print(tsuru) | |
extension String: Potato {} | |
var potatoField = HashedPotatoField<String, Int>(fieldSize: 4) | |
potatoField["ポテト"] = 800 | |
potatoField["さつまいも"] = 1200 | |
potatoField["じゃがいも"] = 50 | |
potatoField["ばれいしょ"] = 250 | |
potatoField["いも"] = 19 | |
print(potatoField) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
あ~い~う~え~* | |
HashedPotatoField<String, Int>(imozuruField: [(key: "いも", imo: 19)~(key: "ばれいしょ", imo: 250)~*, (key: "ポテト", imo: 800)~*, (key: "さつまいも", imo: 1200)~*, (key: "じゃがいも", imo: 50)~*], fieldSize: 4) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment