FilesExpand file tree

 DSA

/

Hash_Map.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

136 lines (116 loc) · 3.23 KB

 DSA

/

Hash_Map.java

Copy path

Top

File metadata and controls

• Code
• Blame

136 lines (116 loc) · 3.23 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

import java.util.*;

public class Hash_Map {

static class HashMap<K,V>{

private class Node {

K key ;

V value ;

public Node (K key , V value ){

this.key = key ;

this.value= value;

}

}

private int n ;

private int N ;

private LinkedList <Node> bucket[];

public HashMap(){

this.N = 4 ;

this.bucket = new LinkedList [4];

for (int i=0 ; i <4 ;i++){

this.bucket[i] = new LinkedList<>();

}

}

// put fuction

public void put (K key , V value ){

int bn = hashFunction (key) ;

int nn = SearchInLL (key , bn);

if (nn == -1){

bucket[bn].add (new Node (key, value));

n++ ;

}

else {

Node Data = bucket[bn].get(nn);

Data.value = value ;

}

double lambda = (double) n/N ;

if (lambda > 2.0){

reHash();

}

}

private int hashFunction (K key){

int bn = key.hashCode() ;

return Math.abs(bn) % N ;

}

private int SearchInLL (K key , int bn){

LinkedList <Node> l = bucket[bn];

for (int i = 0 ; i < l.size() ; i++){

if (l.get(i).key == key){

return i ;

} }

return -1 ;

}

private void reHash(){

LinkedList <Node> oldBucket [] = bucket ;

bucket = new LinkedList[N*2] ;

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

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

}

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

LinkedList <Node> l = oldBucket[i];

for (int j = 0 ; j < l.size() ; j++){

Node node = l.get(j);

put(node.key, node.value);

}

}

}

// 2

public boolean containsKey (K key){

int bn = hashFunction (key) ;

int nn = SearchInLL (key , bn);

if ( nn != -1) {

Node Data = bucket[bn].get(nn);

return true ;

}

return false;

}

//3

public V remove (K key){

int bn = hashFunction (key) ;

int nn = SearchInLL (key , bn);

if ( nn != -1) {

Node Data = bucket[bn].remove(nn);

n--;

return Data.value ;

}

return null;

}

//4

public V get(K key){

int bn = hashFunction (key) ;

int nn = SearchInLL (key , bn);

if ( nn != -1) {

Node Data = bucket[bn].get(nn);

return Data.value ;

}

return null;

}

//5

public ArrayList<K> keySet(){

ArrayList < K> keys = new ArrayList<>();

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

LinkedList< Node> l = bucket[i];

for (int j =0 ; j <l.size() ; j++){

Node node = l.get(i);

keys.add(node.key);

}

}

return keys ;

}

//5

public boolean isEmpty(){

return n == 0 ;

}

}

public static void main(String[] args) {

HashMap <String , Integer> map = new HashMap<>();

}

}