快捷導(dǎo)航

Java實(shí)現(xiàn)簡(jiǎn)易HashMap功能詳解

更新時(shí)間：2020年05月07日 10:17:09 作者：Juily家的小蜜果

這篇文章主要介紹了Java實(shí)現(xiàn)簡(jiǎn)易HashMap功能,結(jié)合實(shí)例形式詳細(xì)分析了Java實(shí)現(xiàn)HashMap功能相關(guān)原理、操作步驟與注意事項(xiàng),需要的朋友可以參考下

創(chuàng)建節(jié)點(diǎn)類

節(jié)點(diǎn)類含有的屬性：鍵值對(duì)（value，key）以及指向下一節(jié)點(diǎn)的next；
這些屬性的get以及set方法

代碼如下：

/**
 * 節(jié)點(diǎn)類
 * @author HP
 *
 */
public class Node {
    private Object value;
    private Object key;
    private Node next;
    
    /**
     * 空節(jié)點(diǎn)
     */
    public Node() {
    }
    
    /**
     * 值為key value的節(jié)點(diǎn)
     * @param data
     */
    public Node(Object key,Object value) {
        this.key = key;
        this.value = value;
    }
    
    
    //接下來就是一些數(shù)據(jù)和節(jié)點(diǎn)的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;
    }

}

實(shí)現(xiàn)MyHash

實(shí)現(xiàn)MyHash的基本操作：

實(shí)現(xiàn)哈希表的基本存取運(yùn)算

1.創(chuàng)建一個(gè)固定大小數(shù)組
2.將數(shù)組中的每個(gè)元素作為頭節(jié)點(diǎn)
存儲(chǔ)鍵值對(duì)
3.存數(shù)：通過對(duì)key某種運(yùn)算，計(jì)算出該數(shù)的哈希碼，將該哈希碼與數(shù)組做某種運(yùn)算，得到該數(shù)在數(shù)組中的哪一個(gè)位置下的鏈表中
4.取數(shù)：計(jì)算該數(shù)的哈希碼，然后同樣找到該數(shù)在數(shù)組中的位置，然后從該頭節(jié)點(diǎn)依次向下進(jìn)行比較得到該數(shù)，不存在則返回null

HashMap的源代碼以及函數(shù)使用方法及返回值：

HashMap hash = new HashMap();
hash.keySet()
hash.hashCode() :返回int類型
hash.put(Object key, Object value)
hash.get(Object key)返回key值對(duì)應(yīng)的value
hash.remove(key) 返回對(duì)應(yīng)的value
hash.remove(key, value) 返回boolean是否remove成功
hash.size() :返回int類型的存儲(chǔ)的節(jié)點(diǎn)的個(gè)數(shù)
hash.containsKey(Object key) :boolean
hash.containsValue(value) :boolean
hash.values() :返回value集合
hash.clear();
hash.replace(key, oldValue, newValue) ???
hash.replace(key, value) 將key對(duì)應(yīng)的oldvalue換為傳入的參數(shù)value，返回oldvalue
hash.entrySet()
hash.isEmpty()
hash.equals(o)：判斷兩個(gè)對(duì)象是否相等，看系統(tǒng)源代碼，可重寫

遍歷Iterator輸出的是所有節(jié)點(diǎn)對(duì)應(yīng)的value的值

存儲(chǔ)的東西越來越大，那么刪除插入操作越來越復(fù)雜,那么需要rehash（需要一個(gè)條件判斷是否需要rehash）

本次示例沒有編寫rehash函數(shù)。

MyHash代碼，注釋還比較詳細(xì)，后邊還有測(cè)試代碼以及測(cè)試結(jié)果：

public class MyHash {
    //哈希數(shù)組的長(zhǎng)度初始化為8
    private int size = 8;
    private int number = 0;//存儲(chǔ)的節(jié)點(diǎn)的個(gè)數(shù)
    //哈希數(shù)組
    private ArrayList<LinkedList> array_head = new ArrayList<LinkedList>(size);
    
    //構(gòu)造方法
    public MyHash() {
        for(int i=0;i<size;i++) {
            LinkedList mylist = new LinkedList();//哈希數(shù)組中初始化存儲(chǔ)的為空鏈表頭
            array_head.add(mylist);//初始化的時(shí)候就將空節(jié)點(diǎn)頭添加到數(shù)組中去
        }
    }
    
    /**
     * 根據(jù) 鍵值對(duì) 生成節(jié)點(diǎn)
     * 將節(jié)點(diǎn)放入哈希表中
     * @param key 鍵
     * @param value 值
     */
    public void put(Object key,Object value) {
        if(number/size == 10) {
            rehash();
        }
        number++;
        Node new_node = new Node(key,value);//由傳入的參數(shù)生成新節(jié)點(diǎn)
        
        int code = hashcode(key.toString());//得到哈希碼
        int position = locate(code);//得到該哈希碼所對(duì)應(yīng)的哈希數(shù)組中的位置
        
        //找到該位置對(duì)應(yīng)的鏈表頭
        LinkedList list_head = (LinkedList) array_head.get(position);
        
        //將節(jié)點(diǎn)放入哈希表中
        list_head.add(new_node);
    }
    
    /**
     * 
     */
    private void rehash() {
        
    }

    /**
     * @param key 
     * @param value
     * @return 返回鍵值對(duì)應(yīng)得節(jié)點(diǎn)
     */
    public Object get(Object key) {
        
        int code = hashcode(key.toString());//得到哈希碼
        int position = locate(code);//得到該哈希碼所對(duì)應(yīng)的哈希數(shù)組中的位置
        
        //找到該位置對(duì)應(yīng)的鏈表
        LinkedList list_head = (LinkedList) array_head.get(position);
        
        //從頭遍歷鏈表 ，找到與鍵key對(duì)應(yīng)的節(jié)點(diǎn)的value值進(jìn)行輸出
        for(int i=0;i<list_head.size();i++) {
            //首先拿到頭節(jié)點(diǎn)
            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的節(jié)點(diǎn)
     * @param key 
     * @return 返回刪除節(jié)點(diǎn)的key對(duì)應(yīng)的value
     */
    public Object remove(Object key) {
        number--;
        int code = hashcode(key.toString());//得到哈希碼
        int position = locate(code);//得到該哈希碼所對(duì)應(yīng)的哈希數(shù)組中的位置
        
        //找到該位置對(duì)應(yīng)的鏈表
        LinkedList list_head = (LinkedList) array_head.get(position);
        
        //從頭遍歷鏈表 ，找到與鍵key對(duì)應(yīng)的節(jié)點(diǎn)的value值進(jìn)行輸出
        for(int i=0;i<list_head.size();i++) {
            //首先拿到頭節(jié)點(diǎn)
            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);//得到該哈希碼所對(duì)應(yīng)的哈希數(shù)組中的位置
        
        //找到該位置對(duì)應(yīng)的鏈表
        LinkedList list_head = (LinkedList) array_head.get(position);
        
        //從頭遍歷鏈表 ，找到與鍵key對(duì)應(yīng)的節(jié)點(diǎn)的value值進(jìn)行輸出
        for(int i=0;i<list_head.size();i++) {
            //首先拿到頭節(jié)點(diǎn)
            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);//得到該哈希碼所對(duì)應(yīng)的哈希數(shù)組中的位置
        
        //找到該位置對(duì)應(yīng)的鏈表
        LinkedList list_head = (LinkedList) array_head.get(position);
        
        //從頭遍歷鏈表 ，找到與鍵key對(duì)應(yīng)的節(jié)點(diǎn)的value值進(jìn)行輸出
        for(int i=0;i<list_head.size();i++) {
            //首先拿到頭節(jié)點(diǎn)
            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) {
        
        //找到該位置對(duì)應(yīng)的鏈表
        
        for(int k=0;k<size;k++) {
            LinkedList list_head = (LinkedList) array_head.get(k);
        
            //從頭遍歷鏈表 ，找到與鍵key對(duì)應(yīng)的節(jié)點(diǎn)的value值進(jìn)行輸出
            for(int i=0;i<list_head.size();i++) {
                //首先拿到頭節(jié)點(diǎn)
                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);//取出每個(gè)節(jié)點(diǎn)
                Node node = head;
                while(node!=null) {
                    //打印出每個(gè)節(jié)點(diǎn)得鍵值對(duì)
                    System.out.print("節(jié)點(diǎn)"+(j+1)+" :("+node.getKey()+":"+node.getValue()+")"+"-->");
                    node = node.getNext();
                }
            }
            System.out.println();
        }
        System.out.println();
    }
    
    /**
     * 
     * @return 返回存儲(chǔ)的節(jié)點(diǎn)的個(gè)數(shù)
     */
    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;
    }
    
    /**
     * 計(jì)算字符串的哈希碼
     * 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;
    }
    
    /**
     * 得到哈希碼對(duì)應(yīng)在數(shù)組中的位置
     * @param k
     * @return
     */
    public int locate(int k) {
        int m = k%size;
        return m;
    }
}

測(cè)試代碼及結(jié)果

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());
        
    }
}