Java中的散列存储

小鱼儿 2022-07-16 11:53 191阅读 0赞

Java中散列存储的数据结构主要是指HashSet、HashMap、LinkedHashSet、LinkedHashMap以及HashTable等。要理解Java中的散列存储机制，那么我们必须先理解两个方法：equals()和hashCode()。关于equals()方法以及其与“==”关系操作符的区别，我们在[另一篇文章][Link 1]中已经说明了。而对于hashCode()，它是在Object类中定义的一个方法：

public native int hashCode();

这是一个返回int值的本地方法，在Object类中没有被实现。这个方法主要被应用于使用散列的数据结构中，配合基于散列的集合一起正常运行，例如，在向一个容器(我们假设是HashMap)中插入一个对象时，怎样判断容器中是否已经存在该对象了呢？由于容器中的元素可能成千上万，使用equals()方法依次进行比较是非常低效的。**散列的价值在于速度**，它将键保存在某处，以便能够很快找到。存储一组元素最快的数据结构是数组，所以使用它来存储键的信息（注意是键的信息，而非键本身）。但是因为数组不能调整容量，因此就有一个问题：我们希望在Map中保存数量不确定的值，但是如果键的数量被数组的容量限制了，该怎么办呢？  
　　答案就是:数组不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是散列码（hashcode），由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成。为解决数组容量被固定的问题，不同的键可以产生相同的下标，这种现象被称为冲突。于是，在容器中查询一个值的过程是：先通过hashCode()计算待插入对象的散列码，然后使用散列码查询数组。对于冲突的处理，常常是通过外部链接，即数组并不直接保存值，而是保存值的list，然后对list中的值进行线性查询，这部分查询自然会比较慢。但是，如果散列函数足够好的话，数组的每个位置就只有较少的值。因此，散列机制便可以快速地跳到数组的某个位置，只对很少的元素进行比较。这就是HashMap会如此快的原因，我们可以通过HashMap.put()方法体会到：

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

其主要思想便是：在键不为空时，根据键对象获取到散列码hash，然后通过散列码得到数组的下标i。在table\[i\]所表示的list中进行迭代，通过equals()判断该键是否存在，如果存在，则用新的值更新旧的值，返回旧的值；否则将新的键值对添加到HashMap中。从这里可以看出，hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。  
　　这里我们需要注意到：hashCode()并不需要总是能够返回唯一的标识码，但是equals()方法必须严格地判断两个对象是否相同。

[Link 1]: http://blog.csdn.net/xiangwanpeng/article/details/52842564