java中哈希表及其应用详解
哈希表也称为散列表,是用来存储群体对象的集合类结构。
什么是哈希表
数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低。
一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录。这就需要在对象的存储位置和对象的关键属性(设为k)之间建立一个特定的对应关系(设为f),使每个对象与一个唯一的存储位置相对应。在查找时,只要根据待查对象的关键属性k计算f(k)的值即可。如果此对象在集合中,则必定在存储位置f(k)上,因此不需要与集合中的其他元素进行比较。称这种对应关系f为哈希(hash)方法,按照这种思想建立的表为哈希表。
Java使用哈希表类(Hashtable)来实现哈希表,以下是与哈希表相关的一些概念:
•容量(Capacity):Hashtable的容量不是固定的,随对象的加入其容量也可以自动增长。
•关键字(Key):每个存储的对象都需要有一个关键字,key可以是对象本身,也可以是对象的一部分(如某个属性)。要求在一个Hashtable中的所有关键字都是唯一的。
•哈希码(HashCode):若要将对象存储到Hashtable上,就需要将其关键字key映射到一个整型数据,成为key的哈希码。
•项(Item):Hashtable中的每一项都有两个域,分别是关键字域key和值域value(存储的对象)。Key和value都可以是任意的Object类型的对象,但不能为空。
•装填因子(LoadFactor):装填因子表示为哈希表的装满程度,其值等于元素数比上哈希表的长度。
哈希表的使用
哈希表类主要有三种形式的构造方法:
Hashtable();//默认构造函数,初始容量为101,最大填充因子0.75
Hashtable(intcapacity);
Hashtable(intcapacity,floatloadFactor)
哈希表类的主要方法如表8-6所示。
表8-6哈希表定义的常见方法
哈希表的创建也可以通过new操作符实现。其语句为:
HashTablehas=newHashTable();
例子:
【例8-12】哈希表的遍历。
//**********ep8_12.java********** importjava.util.*; classep8_12{ publicstaticvoidmain(Stringargs[]){ Hashtablehas=newHashtable(); has.put("one",newInteger(1)); has.put("two",newInteger(2)); has.put("three",newInteger(3)); has.put("four",newDouble(12.3)); Sets=has.keySet(); for(Iterator<String>i=s.iterator();i.hasNext();){ System.out.println(has.get(i.next())); } } }
运行结果:
2 1 3 12.3