質問編集履歴

該当するコードを追加しました。

2018/08/06 05:45

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -17,3 +17,251 @@
 注意:詳細は、-Xlint:uncheckedオプションを指定して再コンパイルしてください。
 ```
+### HashTable
+```Java
+import java.util.List;
+import java.util.LinkedList;
+import java.util.Arrays;
+public class HashTable<K, V> {
+    private Object[] entries;
+    private List<HashTableEntry<K, V>> bucket(int i) {
+        return (List<HashTableEntry<K, V>>)entries[i];
+    }
+    public HashTable(int numBuckets) {
+        if (numBuckets < 1)
+            throw new IllegalArgumentException("hash table must have at least one bucket");
+        this.entries = new Object[numBuckets];
+        for (int i = 0; i < numBuckets; i++)
+            this.entries[i] = new LinkedList<HashTableEntry<K, V>>();
+    }
+    public void put(K key, V value) {
+        HashTableEntry<K, V> e = new HashTableEntry<K, V>(key, value);
+        int h = e.getHashCode();
+        int b = Math.abs(h % this.entries.length);
+        bucket(b).add(e);
+    }
+    public V get(K key) {
+        int h = key.hashCode();
+        int b = Math.abs(h % this.entries.length);
+        for (HashTableEntry<K, V> e : bucket(b))
+            if (key.equals(e.getKey()))
+                return e.getValue();
+        return null;
+    }
+    public boolean includesKey(K key) {
+        int h = key.hashCode();
+        int b = Math.abs(h % this.entries.length);
+        for (HashTableEntry<K, V> e : bucket(b))
+            if (key.equals(e.getKey()))
+                return true;
+        return false;
+    }
+    public boolean includesValue(V value) {
+        int h = value.hashCode();
+        int b = Math.abs(h % this.entries.length);
+        for (HashTableEntry<K, V> e : bucket(b))
+            if (value.equals(e.getValue()))
+                return true;
+        return false;
+    }
+    public List<K> keys() {
+        List<K> klist = new LinkedList<K>();
+        for (int i = 0; i < this.entries.length; i++) {
+            klist = (List<K>)entries[i];
+	}
+        return klist;
+    }
+    public List<V> values() {
+        List<V> vlist = new LinkedList<V>();
+        for (int i = 0; i < this.entries.length; i++) {
+            vlist = (List<V>)entries[i];
+        }
+        return vlist;
+    }
+    public double loadFactor() {
+        double sum = 0;
+        for (int i = 0; i < this.entries.length; i++) {
+            sum += bucket(i).size();
+        }
+        return sum / this.entries.length;
+    }
+    public int numCollisions() {
+        int col = 0;
+        for (int i = 0; i < this.entries.length; i++) {
+            if (bucket(i).size() > 1)
+                col++;
+        }
+        return col;
+    }
+    public int numEmptyBuckets() {
+        int emp = 0;
+        for (int i = 0; i < this.entries.length; i++) {
+            if (bucket(i).isEmpty() == true)
+                emp++;
+        }
+        return emp;
+    }
+    public int maxBucket() {
+        int max = 0;
+        for (int i = 0; i < this.entries.length; i++) {
+            if (bucket(i).size() < bucket(i + 1).size()) {
+                max = bucket(i + 1).size();
+            } else {
+                max = bucket(i).size();
+            }
+        }
+        return max;
+    }
+    public static void main(String[] args) {
+        HashTable<String, Integer> tbl = new HashTable<String, Integer>(10);
+        tbl.put("A", 1);
+        tbl.put("C", 11);
+        tbl.put("B", 2);
+        System.out.println("A:" + tbl.get("A"));
+        System.out.println("C:" + tbl.get("C"));
+        System.out.println("B:" + tbl.get("B"));
+    }
+}
+```