Java中的动态数组、链表和哈希表

作者在 2008-01-25 09:50:57 发布以下内容

        昨天又看了下《Java核心技术》第二卷讲集合类这里,上来说说。
        ArrayList和LinkedList,这是Java中的动态数组和链表。动态数组其实比较简单,就是一个长度可以根据实际情况改变的数组。我们如果要查找某一个动态数组中的元素,可以通过get()方法来查找,只要知道该元素下标就可以了。
        而LinkedList,也就是链表,这个与我们所知道的一般链表稍有不同。一般的链表元素中,除了放这个结点的数据外,还指向下一个结点。一个指向下一个,就这样构成了链表。但是Java中的链表,除了放本来的数据和指向下一个结点外,还指向上一个结点。因此,Java中的LinkedList是双向的。那么有什么用呢?还有就是ArrayList和LinkedList有什么区别?
        这个就要从查找元素的效率和添加删除元素的效率来讲了。在动态数组中,如果我们要在某一个位置添加或者删除一个元素,剩下的每个元素都要相应地往前或往后移动。如果该动态数组中的元素很多,那么,每当我们添加或删除一个元素后,需要移动的元素就非常多,因此,效率就比较低。但是,如果我们使用LinkedList就不一样了。如果我们要在某一个位置添加一个元素,例如,要在A, C之间插入B。本来A是指向C,C也指向A的。现在,只需要将B放到A和C之间,同时让B向前指向A,向后指向C,并且让A从C指向B,让C从A指向B就可以了。如果该链表中元素非常多,我们只需做这个操作就可以了,并不需要移动剩下的元素。所以说LinkedList在添加和删除元素上的效率要比ArrayList高很多。而且,Java中有一个叫ListIterator的迭代器。该迭代器不仅可以向后迭代元素,还能向前迭代,而且还有add()来在某一位置添加元素,十分方便。不过说到查找效率的话就反过来了,是ArrayList的效率比LinkedList的效率高,因为你只要提供元素的下标即可。如果你不知道如何选择ArrayList和LinkedList,就从这两个方面来考虑就行了。
        关于哈希表,该书有一个错误。事实上,Hash表为每个对象计算出一个整数,称为Hash Code(哈希码)。Hash表是个链接式列表的阵列。每个列表称为一个buckets(哈希表元)。对象位置的计算 index = HashCode % buckets (HashCode为对象哈希码,buckets为哈希表元总数)。 这里,书上说先求出index,然后再用对象的哈希码减去这个index就是对象在哈希表中的索引。应该是不要减去的,而且它后面举的例子也没有减去,估计是印刷错误。
        这里转贴一下关于哈希查找的定义: 哈希查找(hashing search)是一种完全不同的查找方法,它不是通过比较确定待查元素的位置,而是在元素的存储位置和它的关键字K之间建立一个对应关系H,使每个关键字K与结构中的一个位置相对应。因而在查找时,只要根据这个对应关系H找到关键字K的存储位置H(K),若结构中存在关键字和K相等的记录,则必定在H(K) 这个存储位置上,因此不需要比较就可直接取得所查记录。称这个对应关系H为哈希函数,H(K)的值为哈希地址或散列地址,按这个思想建立的表为哈希表。
        但实际情况是,对不同的关键字可能根据哈希函数得到相同的地址值,即有:K1≠K2,而H(K1)=H(K2),这种现象称为冲突,具有相同函数值的不同关键字称为同义词。所以在构造哈希表时还应该为发生冲突的关键字另找存储空间。这一过程称为处理冲突的过程。
        上面是关于哈希表的一些介绍。解决冲突的一种常用方法就是链地址法,链地址法处理冲突的方法是:将所有关键字为同义词的数据元素存储在同一链表中。例如,某个对象的哈希码是7,而哈希表元为3,那么7%3=1,因此,该对象就放在哈希表元为1的链表中。如果该表上已经有一个对象了,那么就接着这个对象放在后面就行了。

 

Java | 阅读 12514 次
文章评论,共0条
游客请输入验证码