0jUaZt5C

1/*
2 * To change this license header, choose License Headers in Project Properties.
3 * To change this template file, choose Tools | Templates
4 * and open the template in the editor.
5 */
6package hash;
7
8import java.util.Arrays;
9
10/**
11 * @author LTSACH
12 */
13public class XHashMap<K, V> implements IMap<K, V> {
14    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
15    private Entry<K, V>[] table;
16    private int size;
17    private float loadFactor;
18
19    public XHashMap() {
20        this(10, 0.75f);
21    }
22
23    public XHashMap(int initialCapacity, float loadFactor) {
24        this.table = new Entry[initialCapacity];
25        this.size = 0;
26        this.loadFactor = loadFactor;
27    }
28
29    //////////////////////////////////////////////////////////////////////////
30    /////////////////// Utility methods (private)         ////////////////////
31    ////////////////////////////////////////////////////////////////////////// 
32    private void ensureLoadFactor(int minCapacity) {
33        int maxSize = (int) (this.loadFactor * this.table.length);
34        if ((minCapacity < 0) || (minCapacity > MAX_CAPACITY))
35            throw new OutOfMemoryError("Not enough memory to store the array");
36        if (minCapacity >= maxSize) {
37            //grow: oldCapacity >> 1 (= oldCapacity/2)
38            int oldCapacity = this.table.length;
39            int newCapacity = 2 * oldCapacity;
40            if (newCapacity < 0) newCapacity = MAX_CAPACITY;
41            rehash(newCapacity);
42        }
43    }
44
45    private void rehash(int newCapacity) {
46        Entry<K, V>[] oldTable = this.table;
47        this.table = new Entry[newCapacity];
48        this.size = 0;
49
50        for (Entry<K, V> entry : oldTable) {
51            while (entry != null) {
52                this.put(entry.key, entry.value);
53                entry = entry.next;
54            }
55        }
56    }
57
58    protected int key2index(K key) {
59        return key.hashCode() % this.table.length;
60    }
61
62    //////////////////////////////////////////////////////////////////////////
63    /////////////////// API of XHashMap                    ///////////////////
64    ////////////////////////////////////////////////////////////////////////// 
65
66    @Override
67    public V put(K key, V value) {
68        int index = this.key2index(key);
69        /*YOUR CODE HERE*/
70        ensureLoadFactor(size + 1);
71        Entry<K, V> entry = table[index];
72        if (entry == null) {
73            table[index] = new Entry<>(key, value, null, null);
74        } else {
75//        Find empty entry slot in bucket
76            while (entry.next != null) {
77                entry = entry.next;
78            }
79//        Insert into Bucket
80            entry.next = new Entry<>(key, value, entry, null);
81        }
82        size += 1;
83        return value;
84    }
85
86    @Override
87    public V get(K key) {
88        int index = this.key2index(key);
89        /*YOUR CODE HERE*/
90        Entry<K, V> entry = table[index];
91        while (entry != null) {
92            if (entry.key.equals(key)) {
93                return entry.value;
94            }
95            entry = entry.next;
96        }
97        return null;
98    }
99
100    @Override
101    public V remove(K key) {
102        int index = this.key2index(key);
103        Entry<K, V> entry = this.table[index];
104        while (entry != null) {
105            /*YOUR CODE HERE*/
106            if (entry.key.equals(key)) {
107                size -= 1;
108                if (entry.prev != null) {
109                    entry.prev.next = entry.next;
110                } else {
111                    this.table[index] = entry.next;
112                }
113
114                if (entry.next != null) {
115                    entry.next.prev = entry.prev;
116                }
117
118                entry.next = null;
119                entry.prev = null;
120                return entry.value;
121            }
122            entry = entry.next;
123        }
124        return null;
125    }
126
127    @Override
128    public boolean remove(K key, V value) {
129        int index = this.key2index(key);
130        Entry<K, V> entry = this.table[index];
131        while (entry != null) {
132            if (entry.key.equals(key) && entry.value.equals(value)) {
133                size -= 1;
134                /*YOUR CODE HERE*/
135                if (entry.prev != null) {
136                    entry.prev.next = entry.next;
137                } else {
138                    this.table[index] = entry.next;
139                }
140
141                if (entry.next != null) {
142                    entry.next.prev = entry.prev;
143                }
144
145                entry.next = null;
146                entry.prev = null;
147                return true;
148            }
149            entry = entry.next;
150        }
151        return false;
152    }
153
154    @Override
155    public boolean containsKey(K key) {
156        int index = this.key2index(key);
157        Entry<K, V> entry = this.table[index];
158        while (entry != null) {
159            /*YOUR CODE HERE*/
160            if (entry.key.equals(key)) {
161                return true;
162            }
163            entry = entry.next;
164        }
165        return false;
166    }
167
168    @Override
169    public boolean containsValue(V value) {
170        for (Entry<K, V> entry : this.table) {
171            while (entry != null) {
172                /*YOUR CODE HERE*/
173                if (entry.value.equals(value)) {
174                    return true;
175                }
176                entry = entry.next;
177            }
178        }
179        return false;
180    }
181
182    @Override
183    public boolean empty() {
184        return this.size == 0;
185    }
186
187    @Override
188    public int size() {
189        return this.size;
190    }
191
192    public void println() {
193        System.out.println(this.toString());
194    }
195
196    public String toString() {
197        String desc = String.format("%s\n", new String(new char[50]).replace('\0', '-'));
198        desc += String.format("Capacity: %d\n", this.capacity());
199        desc += String.format("Size: %d\n", this.size());
200        for (int idx = 0; idx < this.table.length; idx++) {
201            Entry<K, V> entry = this.table[idx];
202            String line = String.format("[%4d]:", idx);
203            while (entry != null) {
204                line += String.format("(%s, %s),", entry.key, entry.value);
205                entry = entry.next;
206            }
207            if (line.endsWith(",")) line = line.substring(0, line.length() - 1);
208            desc += line + "\n";
209        }
210        desc += String.format("%s\n", new String(new char[50]).replace('\0', '-'));
211        return desc;
212    }
213
214    /////////////////////////////////////////////////////////
215    ///// The following methods are used for testing only ///
216    /////////////////////////////////////////////////////////
217    public int capacity() {
218        return this.table.length;
219    }
220
221    public int numEntryAt(int index) {
222        Entry<K, V> entry = this.table[index];
223        int count = 0;
224        while (entry != null) {
225            count += 1;
226            entry = entry.next;
227        }
228        return count;
229    }
230}
231
232class Entry<K, V> {
233    K key;
234    V value;
235    Entry<K, V> prev;
236    Entry<K, V> next;
237
238    Entry() {
239        this(null, null, null, null);
240    }
241
242    Entry(K key, V value, Entry<K, V> prev, Entry<K, V> next) {
243        this.key = key;
244        this.value = value;
245        this.prev = prev;
246        this.next = next;
247    }
248}