Erlo

Java实现简易HashMap功能详解

2020-05-07 00:00:00 发布   368 浏览  
页面报错/反馈
收藏 点赞

本文实例讲述了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<LinkedList> array_head = new ArrayList<LinkedList>(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());
        
    }
}

更多java相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总

希望本文所述对大家java程序设计有所帮助。

登录查看全部

参与评论

评论留言

还没有评论留言,赶紧来抢楼吧~~

手机查看

返回顶部

给这篇文章打个标签吧~

棒极了 糟糕透顶 好文章 PHP JAVA JS 小程序 Python SEO MySql 确认