Java實現簡易HashMap功能詳解

創建節點類
節點類含有的屬性：鍵值對（value，key）以及指向下一節點的next；
這些屬性的get以及set方法
代碼如下：
/** * 節點類 * @author HP * */ 

public class Node { private Object value; private Object key; private Node next; 

/** * 空節點 */ public Node() { } 

/** * 值為key value的節點 * @param data */ 

public Node(Object key,Object value) { this.key = key; this.value = value; }

 //接下來就是一些數據和節點的set，get public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } 

public Object getKey() { return key; }

public void setKey(String key) { this.key = key; }

public Node getNext() { return next; } 

public void setNext(Node next) { this.next = next; } }
實現MyHash
實現MyHash的基本操作：
實現哈希表的基本存取運算
1.創建一個固定大小數組
2.將數組中的每個元素作為頭節點
存儲鍵值對
3.存數：通過對key某種運算，計算出該數的哈希碼，將該哈希碼與數組做某種運算，得到該數在數組中的哪一個位置下的鏈表中
4.取數：計算該數的哈希碼，然後同樣找到該數在數組中的位置，然後從該頭節點依次向下進行比較得到該數，不存在則返回null
HashMap的源代碼以及函數使用方法及返回值：
HashMap hash = new HashMap();
hash.keySet()
hash.hashCode() :返回int類型
hash.put(Object key, Object value)
hash.get(Object key)返回key值對應的value
hash.remove(key) 返回對應的value
hash.remove(key, value) 返回boolean是否remove成功
hash.size() :返回int類型的存儲的節點的個數
hash.containsKey(Object key) :boolean
hash.containsValue(value) :boolean
hash.values() :返回value集合
hash.clear();
hash.replace(key, oldValue, newValue) ???
hash.replace(key, value) 將key對應的oldvalue換為傳入的參數value，返回oldvalue
hash.entrySet()
hash.isEmpty()
hash.equals(o)：判斷兩個對象是否相等，看系統源代碼，可重寫
遍歷Iterator輸出的是所有節點對應的value的值
存儲的東西越來越大，那麼刪除插入操作越來越複雜,那麼需要rehash（需要一個條件判斷是否需要rehash）
本次示例沒有編寫rehash函數。
MyHash代碼，註釋還比較詳細，後邊還有測試代碼以及測試結果：
public class MyHash { 

//哈希數組的長度初始化為8 

private int size = 8; private int number = 0;

//存儲的節點的個數 

//哈希數組 

private ArrayList  array_head = new ArrayList(size); 

//構造方法 

public MyHash() { for(int i=0;i<size;i++) { 

LinkedList mylist = new LinkedList();

//哈希數組中初始化存儲的為空鏈表頭 

array_head.add(mylist);

//初始化的時候就將空節點頭添加到數組中去 } } 

/** * 根據 鍵值對 生成節點 

* 將節點放入哈希表中 

* @param key 鍵

* @param value 值 

*/ 

public void put(Object key,Object value) { if(number/size == 10) { rehash(); } number++; Node new_node = new Node(key,value);

//由傳入的參數生成新節點 

int code = hashcode(key.toString());

//得到哈希碼

 int position = locate(code);

//得到該哈希碼所對應的哈希數組中的位置 

//找到該位置對應的鏈表頭 

LinkedList list_head = (LinkedList) array_head.get(position); 

//將節點放入哈希表中 list_head.add(new_node); } 

/** * */ 

private void rehash() { } 

/** * @param key * @param value * @return 返回鍵值對應得節點 */ 

public Object get(Object key) { int code = hashcode(key.toString());

//得到哈希碼 int position = locate(code);//得到該哈希碼所對應的哈希數組中的位置

 //找到該位置對應的鏈表 

LinkedList list_head = (LinkedList) array_head.get(position); 

//從頭遍歷鏈表 ，找到與鍵key對應的節點的value值進行輸出 for(int i=0;i<list_head.size();i++) { 

//首先拿到頭節點 Node head = (Node) list_head.get(i); Node node = head; while(node!=null) { //如果 鍵 相等 if(node.getKey().equals(key)) { 

// System.out.println("node.getValue() :"+node.getValue()); return node.getValue(); 

} 

node = node.getNext(); } }

 return null;

//否則返回空

 }

 /** * 移除鍵為key的節點 * @param key * @return 返回刪除節點的key對應的value */ public Object remove(Object key) { number--; int code = hashcode(key.toString());

//得到哈希碼 int position = locate(code);

//得到該哈希碼所對應的哈希數組中的位置 

//找到該位置對應的鏈表 LinkedList list_head = (LinkedList) array_head.get(position); 

//從頭遍歷鏈表 ，找到與鍵key對應的節點的value值進行輸出 for(int i=0;i<list_head.size();i++) { 

//首先拿到頭節點 

Node head = (Node) list_head.get(i); Node node = head; while(node!=null) { 

//如果 鍵 相等

 if(node.getKey().equals(key)) { Object value = node.getValue(); list_head.remove(node); return value; } node = node.getNext(); } } 

return null;

//否則返回空 } public Object replace(Object key,Object newvalue) { System.out.println("replace"); int code = hashcode(key.toString());

//得到哈希碼 int position = locate(code);

//得到該哈希碼所對應的哈希數組中的位置 

//找到該位置對應的鏈表 LinkedList list_head = (LinkedList) array_head.get(position); 

//從頭遍歷鏈表 ，找到與鍵key對應的節點的value值進行輸出 for(int i=0;i<list_head.size();i++) { 

//首先拿到頭節點 Node head = (Node) list_head.get(i); Node node = head; while(node!=null) { 

//如果 鍵 相等 if(node.getKey().equals(key)) { Object oldvalue = node.getValue(); node.setValue(newvalue); return oldvalue; } node = node.getNext(); } } return null;//否則返回空 } 

/** * @param key 

* @return 哈希表中含有該key，返回true 

*/ 

public boolean containsKey(Object key) { int code = hashcode(key.toString());

//得到哈希碼 

int position = locate(code);

//得到該哈希碼所對應的哈希數組中的位置 

//找到該位置對應的鏈表 

LinkedList list_head = (LinkedList) array_head.get(position); 

//從頭遍歷鏈表 ，找到與鍵key對應的節點的value值進行輸出 for(int i=0;i<list_head.size();i++) { 

//首先拿到頭節點 

Node head = (Node) list_head.get(i); Node node = head; while(node!=null) {

 //如果 鍵 相等

 if(node.getKey().equals(key)) { return true; } 

node = node.getNext(); } } 

return false;//否則返回空 

} 

public Object containsValue(Object value) { //找到該位置對應的鏈表 

for(int k=0;k<size;k++) { 

LinkedList list_head = (LinkedList) 

array_head.get(k);

 //從頭遍歷鏈表 ，找到與鍵key對應的節點的value值進行輸出 for(int i=0;i<list_head.size();i++) {

 //首先拿到頭節點 

Node head = (Node) 

list_head.get(i);

 Node node = head; 

while(node!=null) { //如果 鍵 相等 

if(node.getValue().equals(value)) { return true; } node = node.getNext(); } } } return false;

//否則返回空

 } 

/** * 打印哈希表 */ public void show() { System.out.println("打印哈希表"); for(int i=0;i<size;i++) { LinkedList list_head = array_head.get(i);

//得到鏈表頭

 System.out.println("鏈表 ："+(i+1)); for(int j=0;j<list_head.size();j++) { Node head = (Node) list_head.get(j);//取出每個節點 Node node = head; while(node!=null) { //打印出每個節點得鍵值對 System.out.print("節點"+(j+1)+" :("+node.getKey()+":"+node.getValue()+")"+"-->"); node = node.getNext(); } } System.out.println(); } System.out.println(); } /** * * @return 返回存儲的節點的個數 */ public int size() { return number; } 

/** * 清除哈希表中的所有元素 */ 

public void clear() { for(int i=0;i<size;i++) { LinkedList list_head = array_head.get(i);//得到鏈表頭 list_head.clear(); } number = 0; } 

/** * 計算字符串的哈希碼 * ASCII碼相加 * @param s * @return */ public int hashcode(String s) { int k = 0; for(int i=0;i<s.length();i++) { k += s.charAt(i); } return k; } 

/** * 得到哈希碼對應在數組中的位置 * 

@param k * @return */

 public int locate(int k) { int m = k%size; return m; } }
測試代碼及結果
public class Test { public static void main(String[] args) { MyHash myhash = new MyHash(); myhash.put("abc", 123); myhash.put("b", 2); myhash.put("c", 3); myhash.put("a", 1); myhash.put("d", 4); myhash.put("e", 5); myhash.put("f", 6); myhash.put("g", 7); myhash.put("h", 8); myhash.put("i", 9); myhash.put("j", 10); myhash.put("k", 11); myhash.put("l", 12); myhash.put("m", 13); System.out.println("myhash.get("g") :"+myhash.get("g")); System.out.println("myhash.size() :"+myhash.size()); System.out.println("myhash.replace("m", 20) :"+myhash.replace("m", 20)); System.out.println("myhash.containsValue(5) :"+myhash.containsValue(5)); System.out.println("myhash.containsKey("g") :"+myhash.containsKey("g")); System.out.println("myhash.remove("j") :"+myhash.remove("j")); System.out.println("myhash.show()"); myhash.show(); myhash.clear(); System.out.println("myhash.clear()"); System.out.println("myhash.size() :"+myhash.size()); } }