HashMap快速的原因

ゝ一世哀愁。 2022-05-28 00:44 270阅读 0赞

使用自定义的类作为HashMap的键，必须重载hashCode()和equals()方法，因为这两个方法都是继承自Object类，默认是基于对象地址计算hashCode()和equals()方法。

hashCode()并不需要总是返回唯一的标识码。

HashMap或者HashSet快的原因：

其他查询慢的原因是对于键或者值查询上，因为键或者只没有按特定顺序保存，所以只能采用简单的线性查询，而线性查询是最慢的查询方式。

散列的价值在于速度。由于瓶颈位于键或值的查询速度，因此解决方案之一就是保持键或值的排序状态，然后使用Collections.binarySearch()进行查询。

散列则更进一步，它将键保存在某处，以便能够快速找到。存储一组元素最快的数据结构是数组，所以使用它来表示键的信息，但是数组是固定大小的，我们需要能够保存可变大小的数据。因此数组必须不保存键本身，而是通过键生成一个数字作为数组的下标，这个数字就是散列码，由定义在Object中的、或者是自定义的类覆盖的hashCode()方法生成。

为解决数组容量被固定的问题，不同的键可以生成相同的下标，也就可能产生冲突。因此数组多大就不重要了，任何键在数组中总能找到自己的位置。

于是查询一个值的过程首先就是计算散列码，然后使用散列码查询数组。如果能够保证数组下标没有冲突，那就有了一个完美的散列函数，但这种情况是特例。通常，冲突由外部链接处理：数组并不直接保存只，而是保存值的list，然后对list中的值使用equals()方法进行线性的查询，这也就是为什么HashSet、HashMap存放自定义类需要重写hashCode()和equals()方法的原因。这部分的查询自然会比较慢，但是，如果散列函数好的话，数组的每个位置就会有较少的值。这样就不是查询整个list，而是快速跳转到数组的某个位置，只对较少的元素进行比较。这便是HashMap如此快的原因。

下面实现一个简单的散列Map：

import java.util.Map;
    
    public class MapEntry<K,V> implements Map.Entry<K, V>
    {
        private K key;
        private V value;
        public MapEntry(K key,V value)
        {
            this.key=key;
            this.value=value;
        }
        public K getKey(){
            return key;
        }
        public V getValue(){
            return value;
        }
        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 MapEntry))
            {
                return false;
            }
            MapEntry map=(MapEntry)o;
            return (key==null?map.getKey()==null:key.equals(map.getKey()))
                &&(value==null?map.getValue()==null:value.equals(map.getValue()));
        }
        @Override
        public String toString()
        {
            return key+"="+value;
        }
        
    }

import java.util.*;
    
    public class SimpleHashMap<K,V> extends AbstractMap<K, V>
    {
        static final int SIZE=997;
        LinkedList<MapEntry<K,V>>[] buckets=new LinkedList[SIZE];
        public V put(K key,V value){
            V oldValue=null;
            int index=Math.abs(key.hashCode())%SIZE;
            if (buckets[index]==null)
            {
                buckets[index]=new LinkedList<MapEntry<K, V>>();
            }
            LinkedList<MapEntry<K, V>> bucket=buckets[index];
            MapEntry<K, V> pair=new MapEntry<K, V>(key, value);
            boolean found=false;
            ListIterator<MapEntry<K, V>> it=bucket.listIterator();
            while (it.hasNext())
            {
                MapEntry<K, V> iPair=it.next();
                if (iPair.getKey().equals(key))
                {
                    oldValue=iPair.getValue();
                    it.set(pair);
                    found=true;
                    break;
                }
            }
            if(!found){
                buckets[index].add(pair);
            }
            return oldValue;
        }
        public Set<Map.Entry<K, V>> entrySet(){
            Set<Map.Entry<K, V>> set=new HashSet<Map.Entry<K,V>>();
            for (LinkedList<MapEntry<K, V>> bucket:buckets)
            {
                if(bucket==null) continue;
                for(MapEntry<K, V> mpair:bucket)
                    set.add(mpair);
            }
            return set;
        }
        public static void main(String[] args)
        {
            SimpleHashMap<String, String> m=new SimpleHashMap<String,String>();
            m.put("吉林", "长春");
            m.put("山西", "太原");
            m.put("湖北", "武汉");
            m.put("江苏", "南京");
            m.put("浙江", "杭州");
            m.put("四川", "成都");
            System.out.println(m);
            System.out.println(m.get("浙江"));
            System.out.println(m.entrySet());
        }
    }

执行结果如下：

{江苏=南京,山西=太原, 湖北=武汉, 吉林=长春, 四川=成都, 浙江=杭州}
    
    杭州
    
    [江苏=南京, 山西=太原, 湖北=武汉, 吉林=长春, 四川=成都, 浙江=杭州]

以上内容摘自《Think In Java Edition4》