数据结构之HashMap的实现

﹏ヽ暗。殇╰゛Y 2022-07-13 05:16 155阅读 0赞

Map是数据结构中常用的键值对储存结构，和散列结合的hashMap能够快速的进行查找，这得益于其利用了hashCode进行访问的原因，下边给出一个自己实现的hashMap结构（最后的main是为了测试）。

package jsoup;
    
    import java.util.LinkedList;
    import java.util.List;
    import java.util.ListIterator;
    import java.util.Map;
    
    public class ChainingHashTable<K, V> {
        LinkedList<MyMap<K, V>> linkedList [];
        public ChainingHashTable(int size){
            linkedList = new LinkedList [size];
            for(int i =0; i<linkedList.length; i++) {
                linkedList[i] = new LinkedList<>();
            }
        }
    
        public boolean contain(K x) {
            List<MyMap<K, V>> whichList = linkedList[myhash(x)];
            for(MyMap<K, V> map : whichList){
                if(map.getKey()== x)
                    return true;
            }
            return false;
        }
    
        public V put(K key, V value){
            V oldValue = null;
            boolean found = false;
            List<MyMap<K, V>> whichList = linkedList[myhash(key)];
            MyMap<K, V> myMap = new MyMap<>(key, value);
            ListIterator<MyMap<K, V>> li = whichList.listIterator();
            while(li.hasNext()){
                MyMap<K, V> ipair = li.next();
                if(key.equals(ipair.getKey())){
                    oldValue = ipair.getValue();
                    li.set(myMap);
                    found = true;
                }
            }
            if(! found){
                whichList.add(myMap);
            }
            return oldValue;
        }
    
        public V get(K key){
            V value = null;
            LinkedList<MyMap<K, V>> whichList = linkedList[myhash(key)];
            for(MyMap<K, V> map : whichList){
                if(map.getKey() == key){
                    return map.getValue();
                }
            }
            return value;
        }
    
        public MyMap<K, V> remove(K key){
            MyMap<K, V> map = null;
            LinkedList<MyMap<K, V>> whichList = linkedList[myhash(key)];
            for(MyMap<K, V> map1 : whichList){
                if(map1.getKey() == key){
                    whichList.remove(map1);
                    return map1;
                }
            }
            return map;
        }
    
        private int myhash(K x){
            int hash = x.hashCode();
    
            hash %= linkedList.length;
    
            if(hash < 0)
                hash += linkedList.length;
            return hash;
        }
    
        public static class MyMap<K,V> implements Map.Entry<K, V> {
            private K key;
            private V value;
    
            public MyMap(K key, V value) {
                this.key = key;
                this.value = value;
            }
            @Override
            public K getKey() {
                return key;
            }
    
            @Override
            public V getValue() {
                return value;
            }
    
            @Override
            public V setValue(V v) {
                V result = value;
                value = v;
                return result;
            }
    
            public int hashCode(){
                return (key == null? 0:key.hashCode()) ^ (value == null? 0:value.hashCode());
            }
    
            public boolean equals(Object o) {
                if(!(o instanceof MyMap)) return false;
                MyMap ob = (MyMap)o;
                return (key == null? ob.key == null : key.equals(ob.getKey())) && (value == null? ob.value == null : value.equals(ob.getValue()));
            }
    
            public String toString(){
                return key + "=" + value;
            }
    
        }
    
        //测试
        public static void main(String[] args){
            ChainingHashTable<String, String> map = new ChainingHashTable<>(100);
            map.put("linfujian", "male");
            map.put("vivi", "female");
            System.out.println(map.get("linfujian"));
            System.out.println(map.get("vivi"));
            System.out.println(map.contain("vivi"));
            System.out.println(map.remove("vivi"));
            System.out.println(map.contain("vivi"));
    
        }
    
    }