FilesExpand file tree

master

/

HashMap.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

155 lines (119 loc) · 3.99 KB

master

/

HashMap.java

Copy path

Top

File metadata and controls

• Code
• Blame

155 lines (119 loc) · 3.99 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

package Implementations;

import java.util.Iterator;

public class HashMap<K, V> implements Map<K, V>{

private LinkedList<KeyValuePair<K, V>>[] array = new LinkedList[3];

private int elementsCount = 0;

public HashMap(){

for(int i = 0; i < array.length; i++)

array[i] = new LinkedList<>();

setArraySize(3);

}

private void setArraySize(int size){

LinkedList<KeyValuePair<K, V>> newArray[] = new LinkedList[size];

for(int i = 0; i < size; i++)

newArray[i] = new LinkedList<>();

for(LinkedList<KeyValuePair<K, V>> bucket : array)

for(KeyValuePair<K, V> pair : bucket)

newArray[Math.abs(pair.key.hashCode()) % size].add(pair);

array = newArray;

}

@Override

public void set(K key, V value){

KeyValuePair<K, V> pair = new KeyValuePair<>(key, value);

int bucket = getBucket(key);

int listIndex = array[bucket].getIndex(pair);

if(listIndex == -1) {

array[bucket].add(pair);

elementsCount++;

}

else

array[bucket].get(listIndex).value = pair.value;

if(elementsCount > array.length)

setArraySize(array.length + array.length / 3);

}

@Override

public V get(K key){

KeyValuePair<K, V> pair = new KeyValuePair<>(key, null);

int bucket = getBucket(key);

int listIndex = array[bucket].getIndex(pair);

if(listIndex == -1)

throw new RuntimeException("Key not found: " + key);

return array[bucket].get(listIndex).value;

}

@Override

public void remove(K key){

KeyValuePair<K, V> pair = new KeyValuePair<>(key, null);

int bucket = getBucket(key);

int listIndex = array[bucket].getIndex(pair);

if(listIndex == -1)

throw new RuntimeException("Key not found: " + key);

array[bucket].remove(listIndex);

elementsCount--;

if(elementsCount < array.length - array.length / 3 && elementsCount > 3)

setArraySize(elementsCount);

}

@Override

public boolean contains(K key){

KeyValuePair<K, V> pair = new KeyValuePair<>(key, null);

return array[getBucket(key)].getIndex(pair) != -1;

}

@Override

public int size(){

return elementsCount;

}

@Override

public String toString() {

StringBuilder sb = new StringBuilder("[");

for(int i = 0; i < array.length; i++) {

sb.append(array[i].toString());

if (i < array.length - 1)

sb.append(", ");

}

sb.append("]");

return sb.toString();

}

private int getBucket(K key){

return Math.abs(key.hashCode()) % array.length;

}

@Override

public Iterator<K> keys() {

return new Iterator<K>() {

int currentItem = 0;

int currentIndex = 0;

Iterator<KeyValuePair<K, V>> currentInterator = null;

@Override

public boolean hasNext() {

return currentItem < elementsCount;

}

@Override

public K next() {

currentItem++;

if(currentInterator != null && currentInterator.hasNext())

return currentInterator.next().key;

while(currentIndex < array.length){

currentInterator = array[currentIndex].iterator();

currentIndex++;

if(currentInterator.hasNext())

return currentInterator.next().key;

}

return null;

}

};

}

}

class KeyValuePair<K, V>{

public K key;

public V value;

public KeyValuePair(K key, V value){

this.key = key;

this.value = value;

}

@Override

public boolean equals(Object obj) {

return key.equals(((KeyValuePair<K, V>) obj).key);

}

@Override

public String toString() {

return "{"+ key + ":" + value + "}";

}

}