自己动手实现java数据结构(五)哈希表
副标题[/!--empirenews.page--]
1.哈希表介绍 前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时,有序向量使得我们能使用二分查找法进行精确的查询((O(logN)对数复杂度,很高效)。 1.1 哈希算法哈希算法的定义:把任意长度的输入通过哈希算法转换映射为固定长度的输出,所得到的输出被称为哈希值(hashCode =?hash(input))。哈希映射是一种多对一的关系,即多个不同的输入有可能对应着一个相同的哈希值输出;也意味着,哈希映射是不可逆,无法还原的。 举个例子:我们有一个好朋友叫熊大,大家都叫他老熊。可以理解为是一个hash算法:对于一个人名,我们一般称呼为"老" + 姓氏(单姓) (hash(熊大) = 老熊)。同时,我们还有一个好朋友叫熊二,我们也叫他老熊(hash(熊二) = 老熊)。当熊大和熊二两个好朋友同时和我们聚会时,都称呼他们为老熊就不太合适啦,因为这时出现了hash冲突。老熊这个称呼同时对应了多个人,多个不同的输入对应了相同的哈希值输出。 java在Object这一最高层对象中实现了hashCode方法,并允许子类重写更适应自身,冲突概率更低的hashCode方法。 1.2 哈希表实现的基本思路哈希表存储的是key-value键值对结构的数据,其基础是一个数组。 由于采用hash算法会出现hash冲突,一个数组下标对应了多个元素。常见的解决hash冲突的方法有:开放地址法、重新哈希法、拉链法等等,我们的哈希表实现采用的是拉链法解决hash冲突。 采用拉链法的哈希表将内部数组的每一个元素视为一个插槽(slot)或者桶(bucket),并将数据存放在键值对节点(EntryNode)中。EntryNode除了存放key和value,还维护着一个next节点的引用。为了解决hash冲突,单个插槽内的多个EntryNode构成一个简单的单向链表,插槽指向链表的头部节点,新的数据将会插入当前链表的尾部。 key值不同但映射的hash值相同的元素在哈希表的同一个插槽中以链表的形式共存。
1.3 哈希表的负载因子(loadFactor):哈希表在查询数据时通过直接计算数据hash值对应的插槽,迅速获取到key值对应的数据,进行非常高效的数据查询。 但依然存在一个问题:虽然设计良好的hash函数可以尽可能的降低hash冲突的概率,但hash冲突还是不可避免的。当发生频繁的哈希冲突时,对应的插槽内可能会存放较多的元素,导致插槽内的链表数据过多。而链表的查询效率是非常低的,在极端情况下,甚至会出现所有元素都映射存放在同一个插槽内,此时的哈希表退化成了一个链表,查询效率急剧降低。 一般的,哈希表存储的数据量一定时,内部数组的大小和数组插槽指向的链表长度成反比。换句话说,总数据量一定,内部数组的容量越大(插槽越多),平均下来桶链表的长度也就越小,查询效率越高。 同等数据量下,哈希表内部数组容量越大,查询效率越高,但同时空间占用也越高,这本质上是一个空间换时间的取舍。 哈希表允许用户在初始化时指定负载因子(loadFactor):负载因子代表着存储的总数据量和内部数组大小的比值。插入新数据时,判断哈希表当前的存储量和内部数组的比值是否超过了负载因子。当比值超过了负载因子时,哈希表认为内部过于拥挤,查询效率太低,会触发一次扩容的rehash操作。rehash会对内部数组扩容,将存储的元素重新进行hash映射,使得哈希表始终保持一个合适的查询效率。 通过指定自定义的负载因子,用户可以控制哈希表在空间和时间上取舍的程度,使哈希表能更有效地适应用户的使用场景。 指定的负载因子越大,哈希表越拥挤(负载高,紧凑),查询效率越低,空间效率越高。 指定的负载因子越小,哈希表越稀疏(负载小,松散),查询效率越高,空间效率越低。 2.哈希表ADT接口和之前介绍的链表不同,我们在哈希表的ADT接口中暴露出了哈希表内部实现的EntryNode键值对节点。通过暴露出去的public方法,用户在使用哈希表时,可以获得内部的键值对节点,灵活的访问其中的key、value数据(但没有暴露setKey方法,不允许用户自己设置key值)。 public interface Map <K,V>{ /** * 存入键值对 * @param key key值 * value value * @return 被覆盖的的value值 */ V put(K key,V value); * 移除键值对 * 被删除的value的值 V remove(K key); * 获取key对应的value值 * 对应的value值 V get(K key); * 是否包含当前key值 * true:包含 false:不包含 */ boolean containsKey(K key); * 是否包含当前value值 * value value值 * true:包含 false:不包含 containsValue(V value); * 获得当前map存储的键值对数量 * 键值对数量 * int size(); * 当前map是否为空 * true:为空 false:不为空 isEmpty(); * 清空当前map void clear(); * 获得迭代器 * 迭代器对象 Iterator<EntryNode<K,V>> iterator(); * 键值对节点 内部类 * class EntryNode<K,1)">{ final K key; V value; EntryNode<K,1)"> next; EntryNode(K key,V value) { this.key = key; this.value = value; } keyIsEquals(K key){ if(this.key == key){ return true; } if(key == null){ //:::如果走到这步,this.key不等于null,不匹配 false; }else{ return key.equals(this.key); } } EntryNode<K,1)"> getNext() { return next; } void setNext(EntryNode<K,1)"> next) { this.next =public K getKey() { key; } V getValue() { setValue(V value) { value; } @Override String toString() { return key + "=" + value; } } } 3.哈希表实现细节3.1 哈希表基本属性:class HashMap<K,V> implements Map<K,1)">{ * 内部数组 * private EntryNode<K,1)">[] elements; * 当前哈希表的大小 * private size; * 负载因子 * float loadFactor; * 默认的哈希表容量 * final static int DEFAULT_CAPACITY = 16; * 扩容翻倍的基数 * int REHASH_BASE = 2 * 默认的负载因子 * float DEFAULT_LOAD_FACTOR = 0.75f========================================构造方法=================================================== * 默认构造方法 * @SuppressWarnings("unchecked") HashMap() { this.size = 0; this.loadFactor = DEFAULT_LOAD_FACTOR; elements = new EntryNode[DEFAULT_CAPACITY]; } * 指定初始容量的构造方法 * capacity 指定的初始容量 * public HashMap( capacity) { EntryNode[capacity]; } * 指定初始容量和负载因子的构造方法 * capacity 指定的初始容量 * loadFactor 指定的负载因子 * int capacity, loadFactor) { loadFactor; elements = EntryNode[capacity]; } } 3.2 通过hash值获取对应插槽下标:获取hash的方法仅和数据自身有关,不受到哈希表存储数据量的影响。 (编辑:上饶站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |