文章出處
今天本人想要復習的是哈希表（散列表）的概念及具體實現，為此用java寫了一個簡單的實現，但僅僅只是實現了一些簡單的功能，不過通過這個簡單的實現的確可以幫助我們進一步理解JDK中的HashMap，當然，想要進一步了解就直接閱讀JDK中的HashMap的源碼啦。
實現代碼如下，有注釋，本人就不進一步闡述了：
/** * 該類是HashMap的一個簡單實現。 * * 這里，我主要采用一個元素是鏈表的數組來模擬JDK中的HashMap實現。 當存入一個鍵值對（K,V）的時候，首先計算鍵（K）對應的HashCode。這個HashCode的值其實就是具體實現過程中用到的數組的索引。通過計算鍵的HashCode值便可以知道應該將鍵值對（K,V）存儲在第幾個數組元素中。如前所述，每一個數組元素其實又是一個鏈表。將鍵值對存入散列表其實是存入底層數組元素對應的鏈表結構中。之所以使用鏈表作為數組元素是為了避免HashCode相同但又不相等的鍵造成沖突時候相互覆蓋的問題。這樣就很好的解決了可能存在的碰撞沖突問題。 * * @author lhever * * @param* @param */public class SimpleHashMap { public static final int INITIAL_CAPACITY = 4; private int N; private int M; private SequentialST ,>[] table; /** * 構造 */ public SimpleHashMap() { this(INITIAL_CAPACITY); } /** * 構造，可以指定底層數組的大小 * * @param M */ public SimpleHashMap(int M) { this.M = M; table = (SequentialST ,>[]) new SequentialST[M]; for (int i = 0; i < M; i++) { table[i] = new SequentialST ,>(); } } /** * 重新調整底層數組的大小，從實現的角度看，所有已經 存入的鍵值對會被從新計算散列值并調整存儲的位置。 * * @param newSize */ private void resize(int newSize) { SimpleHashMap ,>temp = new SimpleHashMap ,>(newSize); for (int i = 0; i < M; i++) { for (K key : table[i].keys()) { temp.put(key, table[i].get(key)); } } this.M = temp.M; this.N = temp.N; this.table = temp.table; } private int hash(K key) { return (key.hashCode() & 0x7fffffff) % M; } public int size() { return N; } public boolean isEmpty() { return size() == 0; } public boolean contains(K key) { if (key == null) { throw new NullPointerException("參數不能為null"); } return get(key) != null; } public V get(K key) { if (key == null) { throw new NullPointerException("參數不能為null"); } int i = hash(key); return table[i].get(key); } public void put(K key, V val) { if (key == null) { throw new NullPointerException("key不能為null"); } if (val == null) { remove(key); return; } // 當鏈表中的平均元素個數大于10的時候增加底層數組的大小（變為兩倍大） if (N >= 10 * M) { resize(2 * M); } int i = hash(key); if (!table[i].contains(key)) { N++; } table[i].put(key, val); } public void remove(K key) { if (key == null) { throw new NullPointerException("參數不能為null"); } int i = hash(key); if (table[i].contains(key)) { N--; table[i].delete(key); } // 如果列表中的平均元素個數小于等于2的時候，降低底層數組的大小（變為原來大小的1/2） if (M > INITIAL_CAPACITY && N <= 2 * M) { resize(M / 2); } } // 返回一個迭代器，其中包含了所有的鍵 public Iterable ,>keys() { Queue queue = new LinkedList (); for (int i = 0; i < M; i++) { for (K key : table[i].keys()) queue.offer(key); } return (Iterable ) queue; } /** * 測試 * * @param args */ public static void main(String... args) { SimpleHashMap map = new SimpleHashMap (); map.put("country", "China"); map.put("level", "super"); map.put("nature", "public"); System.out.println(map.get("country")); System.out.println("befor remove, the size is: " + map.size()); map.remove("country"); System.out.println("after remove, the size is: " + map.size()); for (String key : (Iterable ,>) map.keys()) { System.out.println(key + " : " + map.get(key)); } map.remove("nature"); map.remove("level"); map.remove("level"); System.out.println("after remove, the size is: " + map.size()); for (String key : (Iterable ) map.keys()) { System.out.println(key + " : " + map.get(key)); } map.put("size", "960"); System.out.println("after put, the size is: " + map.size()); }}////////////////////////////////////////////////////package lhever.Hash_Map;import java.util.LinkedList;import java.util.Queue;/** * 該類是一個順序查找的鏈表實現，查找元素時候會從第一個節點開始順序查找， * 該鏈表實現會被用到SimpleHashMap（JDK中HashMap的一個簡單實現）的實現中 * * @author lhever * * @param * @param */public class SequentialST { private int N; private Node first; /** * 代表一個節點 * * @author lhever */ private class Node { private K key; private V value; private Node next; public Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; } } public SequentialST() { } public int size() { return N; } public boolean isEmpty() { return size() == 0; } public boolean contains(K key) { if (key == null) throw new NullPointerException("參數不能為null"); return get(key) != null; } /** * 查找從第一個節點開始順序進行 * * @param key * @return */ public V get(K key) { if (key == null) throw new NullPointerException("參數不能為null"); for (Node node = first; node != null; node = node.next) { if (key.equals(node.key)) return node.value; } return null; } /** * 增加 * * @param key * @param value */ public void put(K key, V value) { if (key == null) throw new NullPointerException("參數不能為null"); if (value == null) { delete(key); return; } for (Node node = first; node != null; node = node.next) { if (key.equals(node.key)) { node.value = value; return; } } first = new Node(key, value, first); N++; } public void delete(K key) { if (key == null) throw new NullPointerException("參數不能為null"); first = delete(first, key); } private Node delete(Node node, K key) { if (node == null) return null; if (key.equals(node.key)) { N--; return node.next; } node.next = delete(node.next, key); return node; } public Iterable ,>keys() { Queue queue = new LinkedList (); for (Node node = first; node != null; node = node.next) queue.offer(node.key); return queue; }}
看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161027/11056.html
文章列表
全站熱搜
留言列表
