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
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
case Nil :: xs => forIsEmpty(xs)
case _ => false
}
def isEmpty() : Boolean = {
forIsEmpty(arrayOfBoxes)
}
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();
}