java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言, 是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台 (即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se)) 的总称
这篇文章主要介绍了 Java 散列存储详解及简单示例的相关资料, 需要的朋友可以参考下
Java 散列存储
Java 中散列存储的数据结构主要是指 HashSetHashMapLinkedHashSetLinkedHashMap 以及 HashTable 等要理解 Java 中的散列存储机制, 那么我们必须先理解两个方法: equals()和 hashCode()关于 equals()方法以及其与 == 关系操作符的区别, 我们在另一篇文章中已经说明了而对于 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()方法必须严格地判断两个对象是否相同
来源: http://www.phperz.com/article/18/0217/358640.html