寒光博客

[java] HashMap的简单实现
MyHashMap Map Interface keySet 主要作用于HashSet package _10_H...
扫描右侧二维码阅读全文
06
2019/11

[java] HashMap的简单实现

MyHashMap

Map Interface

keySet 主要作用于HashSet

package _10_Hash;

import java.util.Iterator;

public interface IMap<K, V> {
    /**
     * 清除所有键值对
     */
    void clear();

    /**
     * key是否已存在
     *
     * @param key
     * @return
     */
    boolean containsKey(K key);

    /**
     * value是否已存在
     *
     * @param value
     * @return
     */
    boolean containsValue(V value);

    /**
     * 根据key获得valye
     *
     * @param key
     * @return
     */
    V get(K key);

    /**
     * map  是否为空
     *
     * @return
     */
    boolean isEmpty();

    /**
     * 所有 key组成的数组
     * 和java api区分 所以用数组
     *
     * @return
     */
    MyHashSet<K> keySet();

    /**
     * 存入键值对
     *
     * @param key
     * @param value
     * @return
     */
    void put(K key, V value);

    /**
     * 把另外一个map中的所有键值对 存入到当前map中
     *
     * @param map
     */
    void putAll(IMap<? extends K, ? extends V> map);

    /**
     * 根据key删除一个键值对
     * @param key
     * @return
     */
    V remove(K key);

    /**
     * 键值对的个数
     * @return
     */
    int size();

    /**
     * 所有的value组成的数组
     * @return
     */
    V[] values();

    /**
     * 迭代器
     * @return
     */
    Iterator<MyHashMap.Node> iterator();

}

MyHashMap

这里用拉链法实现 put
迭代器的实现算法比较关键~~

package _10_Hash;

import java.util.Iterator;

public class MyHashMap<K,V> implements IMap<K,V> {

    /**
     * Node节点
     *
     * @param <K>
     * @param <V>
     */
    public static class Node<K, V> {
        K key;
        V value;
        Node next;

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

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    //创建桶
    int N = 16;
    private Node[] buckets = new Node[N];
    private int size = 0;



    @Override
    public void clear() {
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = null;
        }
        size=0;

    }

    @Override
    public boolean containsKey(K key) {
        int index = hash1(key);
        if (buckets[index] == null)//查看有没有对应的桶
            return false;
        else {
            Node<K, V> p = buckets[index];//在链表中找key
            while (p != null) {
                K k1 = p.key;
                //借用java机制 hashCode和 equals都来源与 Object 用户可以改写这两个方法制定对象相等的原则
                //k1==key 比较的是对象的地址 java 默认 hashCode和equals都是基于对象地址
                if (k1 == key || k1.hashCode() == key.hashCode() && k1.equals(key)) {
                    return true;
                }
                p = p.next;
            }
        }
        return false;
    }

    @Override
    public boolean containsValue(Object value) {
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                Node<K, V> p = buckets[i];
                while (p != null) {
                    if (p.value.equals(value))
                        return true;
                    p = p.next;
                }
            }

        }
        return false;
    }

    @Override
    public V get(K key) {
        int index = hash1(key);//先看看有没有这个key的桶
        if (buckets[index] == null) {
            return null;
        } else {
            Node<K, V> p = buckets[index];
            while (p != null) {
                K k1 = p.key;
                if (k1 == key || k1.equals(key) && k1.hashCode() == key.hashCode()) {
                    return p.value;
                }
                p = p.next;
            }
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public MyHashSet<K> keySet() {
        MyHashSet<K> set = new MyHashSet<>();
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                Node<K, V> p = buckets[i];
                while (p != null) {
                    set.add(p.key);
                    p = p.next;
                }
            }
        }
        return set;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                Node<K, V> p = buckets[i];
                while (p != null) {
                    sb.append("(" + p.key + "," + p.value + ")" + ",");
                    p = p.next;
                }
            }
        }
        return sb.toString();
    }

    /**
     * 解决冲突的时候使用拉链法
     * 相同替换 不同就追加
     * @param key
     * @param value
     */
    @Override
    public void put(K key, V value) {
        Node<K, V> node = new Node<>(key, value);
        int index = hash1(key);//算出在桶中的位置
        if (buckets[index] == null) {//桶子中没有东西 确定链表的表头
            buckets[index] = node;
            size++;
        } else {
            Node<K, V> p = buckets[index];//链表的表头找到
            while (p != null) {//遍历链表 从头开始
                K k1 = p.key;
                if (key == k1 || key.hashCode() == k1.hashCode() && key.equals(k1)) {//存在key相同就覆盖
                    p.value = value;//存在相同的key 则更新value
                    break;
                }
                if (p.next == null) {//最后一个
                    p.next = node;
                    size++;
                    break;
                }
                p = p.next;// 没有 相同key  也不是最后一个 指针后移
            }

        }

    }

    /**
     * 算出在桶中的位置
     *
     * @param key
     * @return
     */
    private int hash1(K key) {
        return key.hashCode() % N;
    }

    @Override
    public void putAll(IMap<? extends K, ? extends V> map) {

    }

    @Override
    public V remove(K key) {
        int index = hash1(key);
        if (buckets[index] == null) {
            return null;
        } else {
            //单向链表移除某个节点需要两个指针
            Node<K, V> p = buckets[index];//表头
            Node<K, V> pre = p;
            while (p != null) {
                K k1 = p.key;
                if (k1 == key || k1.hashCode() == key.hashCode() && k1.equals(key)) {
                    //匹配到了移除
                    if (p == pre) {//是头结点
                        buckets[index] = pre.next;//buckets[index]相当于单链表的first
                    } else {
                        pre.next = p.next;//原本 pre.next==p
                    }
                    size--;
                    return p.value;
                }
                pre = p;
                p = p.next;
            }
        }

        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public V[] values() {
        return null;
    }

    //内部类迭代器
    private class MapIterator implements Iterator<MyHashMap.Node> {
        int i = 0;
        Node p = buckets[0];

        @Override
        public boolean hasNext() {
            while (p == null && i < N) {
                i++;
                if (i == N)
                    p = null;
                else
                    p = buckets[i];
            }
            //i是一个非空的桶子 p是链表头
            return p != null;
        }

        @Override
        public Node next() {
            Node res = p;
            p = p.next;
            return res;
        }
    }

    @Override
    public Iterator<MyHashMap.Node> iterator() {
        return new MapIterator();

    }
}

Test

package _10_Hash;

import org.junit.Before;
import org.junit.Test;

import java.util.Iterator;

public class MyHashSetTest {
    MyHashSet<Integer> set = new MyHashSet<>();

    @Before
    public void add() {
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(1);

    }

    @Test
    public void remove() {
        System.out.println(set);
        set.remove(1);
        System.out.println(set);

    }

    @Test
    public void clear() {
        set.clear();
        System.out.println(set);
    }

    @Test
    public void contains() {
        System.out.println(set.contains(1));
        System.out.println(set.contains(66));
    }

    @Test
    public void isEmpty() {
        System.out.println(set.isEmpty());
        set.clear();
        System.out.println(set.isEmpty());
    }

    @Test
    public void size() {
        System.out.println(set.size());
        set.remove(1);
        System.out.println(set.size());
        System.out.println(set);
        set.clear();
        System.out.println(set.size());
        System.out.println(set);

    }

    @Test
    public void iter() throws Exception {
        Iterator<Integer> iter = set.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next());
        }
    }

}

HashFunctions

关于Hash的各种求法
提高key的分散程度~

简单版的优化空间

java HashMap 优化

本文作者:Author:     文章标题:[java] HashMap的简单实现
本文地址:https://dxoca.cn/java/312.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:November 8th, 2019 at 02:22 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment