黑马程序员技术交流社区

标题: 【上海校区】Java简单实现自定义HashMap [打印本页]

---

作者: 不二晨    时间: 2019-2-22 16:54
标题: 【上海校区】Java简单实现自定义HashMap
数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。
要综合两者的特性，就有了哈希表。哈希表有多种不同的实现方法,最经典的一种方法 —— 拉链法。
哈希表可以理解为链表的数组。主干为数组，数组的每一个成员是链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是哈希算法。
节点类中需要的属性key,value，指向下一个节点

节点类

public class Node{
        private Object key;
        private Object value;
        private Node next;
        public Node(){
        }
        public Node(Object key, Object value) {
                super();
                this.key = key;
                this.value = value;
        }
        public Node getNext(){
                return next;
        }
        public void setKey(String s){
                this.key=s;
        }
        public void setValue(Object value){
                this.value=value;
        }
        public Object getKey() {
                return key;
        }
        public Object getValue() {
                return value;
        }
       
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
主要实现
hash.hashCode() :返回int类型
hash.put(Object key, Object value)
hash.get(Object key)返回key值对应的value
hash.remove(key) 返回对应的value
hash.replace(key, value) 返回boolean是否remove成功
hash.size() :返回int类型的存储的节点的个数
hash.containsKey(Object key) :boolean
hash.containsValue(value) :boolean

自定义Map类

public class MyHashMap {
        private int size = 8;
        private int number = 0;// 存储的节点的个数
        private ArrayList<LinkedList> array_head = new ArrayList<LinkedList>(size);

        public MyHashMap() {
                super();
                for (int i = 0; i < size; i++) {
                        LinkedList list = new LinkedList();// 哈希数组中初始化存储的为空链表头
                        array_head.add(list);// 初始化的时候就将空节点头添加到数组中去
                }

        }

        /**
         * 根据 键值对 生成节点 将节点放入哈希表中
         *
         * @param key
         *            键
         * @param value
         *            值
         */
        public void put(Object key, Object value) {
                if (containsKey(key) == true) {// 判断是否已经存在该key值,如果存在，直接替换该value值
                        replace(key, value);
                } else {// 不存在，创建一个新的key值
                        if (number / size == 10) {
                                rehash();
                        }
                        number++;
                        Node node = new Node(key, value);
                        int code = hashcode(key.toString());// 得到哈希码
                        int index = locate(code);// 得到该哈希码在对应哈希数组中的位置

                        // 找到对应位置的链表头
                        LinkedList<Node> list_head = array_head.get(index);
                        list_head.add(node);// 将节点放进链表中
                }
        }

        /**
         * 打印哈希表
         */
        public void show() {
                System.out.println("打印哈希表");
                for (int i = 0; i < size; i++) {
                        LinkedList link_head = array_head.get(i);// 得到链表头
                        System.out.println("链表：" + i);
                        for (int j = 0; j < link_head.size(); j++) {
                                Node node = (Node) link_head.get(j);// 打印每个节点
                                while (node != null) {
                                        // 打印出没个节点对应的键值对
                                        System.out.print("节点" + (j + 1) + ":" + "<" + node.getKey() + "," + node.getValue() + ">" + "  ");
                                        node = node.getNext();

                                }

                        }
                        System.out.println();
                }

        }

        /**
         * 根据键得到值
         */
        public Object getValue(Object key) {
                // 根据key值找到数组对应位置
                int code = hashcode(key.toString());
                int index = locate(code);
                LinkedList list = array_head.get(index);
                // 从头遍历，找到与键key对应节点的value值进行输出
                for (int i = 0; i < list.size(); i++) {
                        Node node = (Node) list.get(i);
                        while (node != null) {
                                if (node.getKey().equals(key)) {
                                        return node.getValue();
                                }
                                node = node.getNext();
                        }

                }
                return null;

        }

        /**
         * 移除节点
         *
         * @param key
         * @return
         */
        public boolean remove(Object key) {
                number--;
                int code = hashcode(key.toString());
                int index = locate(code);
                LinkedList list = array_head.get(index);

                for (int i = 0; i < list.size(); i++) {
                        Node node = (Node) list.get(i);
                        while (node != null) {
                                if (node.getKey().equals(key)) {
                                        list.remove(i);
                                        return true;
                                }
                                node = node.getNext();
                        }
                }
                return false;
        }

        /**
         * 替换key键处的value值
         *
         * @param key
         * @param value
         * @return
         */
        public boolean replace(Object key, Object value) {
                // 根据key值找到数组对应位置
                int code = hashcode(key.toString());
                int index = locate(code);
                LinkedList list = array_head.get(index);
                for (int i = 0; i < list.size(); i++) {
                        Node node = (Node) list.get(i);
                        if (node.getKey().equals(key)) {
                                node.setValue(value);
                                return true;
                        }
                }

                return false;
        }

        /**
         * 清空方法
         */
        public void clear() {
                for (int i = 0; i < size; i++) {
                        LinkedList list = array_head.get(i);
                        list.clear();
                }
                number = 0;
        }

        /**
         * 哈希表中含key键，返回true
         *
         * @param key
         * @return
         */

        public boolean containsKey(Object key) {
                // 根据key值找到数组对应位置
                int code = hashcode(key.toString());
                int index = locate(code);
                LinkedList list = array_head.get(index);
                for (int i = 0; i < list.size(); i++) {
                        Node node = (Node) list.get(i);
                        if (node.getKey().equals(key)) {
                                return true;
                        }
                        node = node.getNext();
                }

                return false;
        }

        /**
         * 哈希表中含value值，返回true
         *
         * @param value
         * @return
         */
        public boolean containsValue(Object value) {
                // 找到该对应位置的链表
                for (int i = 0; i < size; i++) {
                        LinkedList list = array_head.get(i);
                        // 从头遍历，找到与键key对应节点的value值进行输出
                        for (int j = 0; j < list.size(); j++) {
                                Node node = (Node) list.get(j);
                                while (node != null) {
                                        if (node.getValue().equals(value)) {
                                                return true;
                                        }
                                        node = node.getNext();
                                }

                        }
                }
                return false;
        }

        private void rehash() {

        }

        /**
         * 计算字符串的哈希码 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 int size() {
                return number;
        }

}
---------------------
【转载，仅作分享，侵删】
作者：lzq1326253299
原文：https://blog.csdn.net/lzq1326253299/article/details/87368297
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-2-26 15:32
奈斯，感谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2