Задумал я реализовать свой HashMap для показательного примера, в два этапа:
- реализовать словарь максимально просто
- затем улучшить производительность до уровня HashMap, добавить разбиение на баккеты и использовать хешкоды
Но вышло так что моя простая реализация Map оказалась такой же шустрой как и HashMap, даже без разбиения на баккеты, в некоторых кейсах даже шустрее :)
Вот и вся реализация:
classMap<T> {
val values = mutableListOf<T>()
val keys = mutableListOf<Any>()
funadd(key:Any, value:T) {
keys.add(key)
values.add(keys.size -1, value)
}
funremove(key:Any) {
val i = keys.indexOf(key)
values.removeAt(i)
keys.remove(key)
}
operatorfunset(key:Any, value:T) {
val i = keys.indexOf(key)
values[i] = value
}
operatorfunget(key:Any): T? {
val i = keys.indexOf(key)
return (if (i <0) nullelse values[i])
}
}Там еще тесты есть.