class KeyValue val key val value override def toString String key valu

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
class KeyValue[K, V](val key: K, val value: V) {
override def toString(): String = "(" + key + ", " + value + ")";
}
class HashMap[K, V>:Null] private (val lengthOfList: Int, val arrayOfBoxes: List[List[KeyValue[K,V]]]) {
// мощность хз зачем
def this(capacity: Int) = this(capacity, Nil);
// вычисление хэш функции от ключа по модулю длинны таблицы
private def hFunc(key: K) : Int = {
key.hashCode() % lengthOfList;
}
// определение на пустоту
private def forIsEmpty(arrayOfBoxes: List[List[KeyValue[K,V]]]) : Boolean = arrayOfBoxes match {
case Nil => true // если последнего нет, то возвращаем 1
case Nil :: xs => forIsEmpty(xs)// если текущего нет, для следующего
case _ => false // если есть элемент, то возвращаем 0
}
def isEmpty() : Boolean = {
forIsEmpty(arrayOfBoxes)// если определение на пустоту даёт 1, возвращаем 1, иначе 0
}
// проверка на содержание (наличие в таблице значения по ключу)
private def forContainsKey(list: List[KeyValue[K, V]], key: K) : Boolean = (list, key) match {
case (Nil, key) => false // если таблица окончена, то не содержит
case (x :: xs, key) if (x.key == key) => true // если не окончена, то если текущий совпадает с тем что ищем, то содержит
case (x :: xs, key) => forContainsKey(xs, key) // иначе переходим к следующему
}
def containsKey(key: K) : Boolean = {
if (forIsEmpty(arrayOfBoxes)) false //если таблица пуста то не содержится
else if (arrayOfBoxes(hFunc(key)) == Nil) false // если хэшфункция от ключа ничего не возвращает то не сожержитвся !!!ХЗ
else forContainsKey(arrayOfBoxes(hFunc(key)), key)//иначе возвращаем результат проверки на содержание
}
// получение значения по ключу
private def forGetValue(list: List[KeyValue[K, V]], key: K) : V = (list, key) match {
case (Nil, key) => null // если таблица окончена, то не содержится ключа
case (x :: xs, key) if (x.key == key) => x.value
case (x :: xs, key) => forGetValue(xs, key)
}
def getValue(key: K) : V = {
if (!containsKey(key)) null
else forGetValue(arrayOfBoxes(hFunc(key)), key)
}
private def initEmptyMap(numOfList: Int, curNum: Int, key: K, value: V) : List[List[KeyValue[K,V]]] = {
if (curNum < lengthOfList) {
if (numOfList == curNum) {
val pair = new KeyValue[K, V](key, value);
val list: List[KeyValue[K, V]] = pair :: Nil;
list :: initEmptyMap(numOfList, curNum+1, key, value)
} else Nil :: initEmptyMap(numOfList, curNum+1, key, value)
} else Nil
}
private def initMap(numOfList: Int, curNum: Int, key: K, value: V) : List[List[KeyValue[K,V]]] = {
if (curNum < lengthOfList) {
if (numOfList == curNum) {
val pair = new KeyValue[K, V](key, value);
val oldList: List[KeyValue[K, V]] = arrayOfBoxes(hFunc(key));
val newList: List[KeyValue[K, V]] = pair :: oldList;
newList :: initMap(numOfList, curNum+1, key, value);
} else arrayOfBoxes(curNum) :: initMap(numOfList, curNum+1, key, value);
} else Nil;
}
def insert(key: K, value: V) : HashMap[K, V] = {
if (arrayOfBoxes == Nil || forIsEmpty(arrayOfBoxes))
new HashMap[K, V](lengthOfList, initEmptyMap(hFunc(key), 0, key, value))
else if (containsKey(key)) this
else new HashMap[K, V](lengthOfList, initMap(hFunc(key), 0, key, value))
}
private def deletePair(key: K, oldList: List[KeyValue[K, V]]) : List[KeyValue[K, V]] = (key, oldList) match {
case (key, Nil) => Nil
case (key, x :: xs) if (x.key == key) => deletePair(key, xs)
case (key, x :: xs) => x :: deletePair(key, xs)
}
private def initMapForDelete(numOfList: Int, curNum: Int, key: K) : List[List[KeyValue[K,V]]] = {
if (curNum < lengthOfList) {
if (numOfList == curNum) {
val newList: List[KeyValue[K, V]] = deletePair(key, arrayOfBoxes(numOfList));
newList :: initMapForDelete(numOfList, curNum+1, key);
} else arrayOfBoxes(curNum) :: initMapForDelete(numOfList, curNum+1, key);
} else Nil;
}
def delete(key: K) : HashMap[K, V] = {
if (arrayOfBoxes == Nil || forIsEmpty(arrayOfBoxes)) this
else if (!containsKey(key)) this
else new HashMap[K, V](lengthOfList, initMapForDelete(hFunc(key), 0, key))
}
override def toString(): String = arrayOfBoxes.toString();
}