ハッシュテーブルの実装

HashedPotatoField.swift

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)

出力

あ~い~う~え~*
HashedPotatoField<String, Int>(imozuruField: [(key: "いも", imo: 19)~(key: "ばれいしょ", imo: 250)~*, (key: "ポテト", imo: 800)~*, (key: "さつまいも", imo: 1200)~*, (key: "じゃがいも", imo: 50)~*], fieldSize: 4)