欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java 散列存储详解及简单示例

程序员文章站 2024-03-08 11:20:42
java 散列存储  java中散列存储的数据结构主要是指hashset、hashmap、linkedhashset、linkedhashmap以及hashtable等。...

java 散列存储

 java中散列存储的数据结构主要是指hashset、hashmap、linkedhashset、linkedhashmap以及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()方法必须严格地判断两个对象是否相同。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!