貌似每次写博客之前就得先说说自己又多久多久没有写过博客了,这次的博客距上次的已经过了快一年了,确实自制力不够,懒癌加拖延症患者伤不起。
咳咳,接下来进入正题:数据结构已经很让人头疼了,不过更让人头疼的还有hash。那么什么是hash?
全称:hash table
简写:HT
中文名:散列表
结构:hash table中的一个位置叫做一个槽(怎么就感觉像是个坑),注意了:一个槽里只能放一个数据,槽的数量姑且用M表示,则一个hash table中就有用0—M-1编号的M个槽(不同hash table的结构不同,其中有一种就是在这个名为“槽”的坑里再挖若干个坑,要不然装不下我们要装的东西)。
怎么用:这里又涉及到名为“散列函数”的东西(不用知道它具体是什么样的,因为它具有变色龙的性质,知道它是一个函数就好),我们利用这个散列函数(实际上就是通过一系列的计算),将我们要保存的数据放到那一个一个坑里去。那么问题来了,要是坑里已经放了一个数据了,新数据通过计算之后又是应该放在那个坑里的,放不下怎么办,这样上面说的坑里再挖坑就排上用场了(当然不止这一种方法哦),这里,坑里再挖的坑由于需要有一定的灵活性,我们通常用链表来实现。
通过以上简介,我们大概知道了hash table的大概情况了,接下来,上手了,代码来也~
/** * 存 * @param k * @param v */ public boolean put(K k, V v) { // 1.计算K的hash值 // 直接调用JDK给出的hashCode()方法来计算hash值 int hash = k.hashCode(); //将所有信息封装为一个Entry Entry< K,V> temp=new Entry(k,v,hash); if(setEntry(temp, container)){ // 大小加一 size++; return true; } return false; }
/** * 取 * @param k * @return */ public V get(K k) { Entry< K, V> entry = null; // 1.计算K的hash值 int hash = k.hashCode(); // 2.根据hash值找到下标 int index = indexFor(hash, container.length); // 3.根据index找到链表 entry = container[index]; // 4.若链表为空,返回null if (null == entry) { return null; } // 5.若不为空,遍历链表,比较k是否相等,如果k相等,则返回该value while (null != entry) { if (k == entry.getKey()||entry.getKey().equals(k)) { return entry.getValue(); } entry = entry.getNext(); } // 如果遍历完了不相等,则返回空 return null; }
/** *将指定的结点temp添加到指定的hash表table当中 * 添加时判断该结点是否已经存在 * 如果已经存在,返回false * 添加成功返回true * @param temp * @param table * @return */ private boolean setEntry(Entry< K,V> temp,Entry[] table){ // 根据hash值找到下标 int index = indexFor(temp.getHash(), table.length); //根据下标找到对应元素 Entry< K, V> entry = table[index]; // 3.若存在 if (null != entry) { // 3.1遍历整个链表,判断是否相等 while (null != entry) { //判断相等的条件时应该注意,除了比较地址相同外,引用传递的相等用equals()方法比较 //相等则不存,返回false if ((temp.getKey() == entry.getKey()||temp.getKey().equals(entry.getKey())) && temp.getHash() == entry.getHash()&&(temp.getValue()==entry.getValue()||temp.getValue().equals(entry.getValue()))) { return false; } else if(temp.getKey() == entry.getKey() && temp.getValue() != entry.getValue()) { entry.setValue(temp.getValue()); return true; } //不相等则比较下一个元素 else if (temp.getKey() != entry.getKey()) { //到达队尾,中断循环 if(null==entry.getNext()){ break; } // 没有到达队尾,继续遍历下一个元素 entry = entry.getNext(); } } // 3.2当遍历到了队尾,如果都没有相同的元素,则将该元素挂在队尾 addEntry2Last(entry,temp); return true; } // 4.若不存在,直接设置初始化元素 setFirstEntry(temp,index,table); return true; }
/** * 扩容 * @param newSize 新的容器大小 */ private void reSize(int newSize) { // 1.声明新数组 Entry< K, V>[] newTable = new Entry[newSize]; max = (int) (newSize * LOAD_FACTOR); // 2.复制已有元素,即遍历所有元素,每个元素再存一遍 for (int j = 0; j < container.length; j++) { Entry< K, V> entry = container[j]; //因为每个数组元素其实为链表,所以………… while (null != entry) { setEntry(entry, newTable); entry = entry.getNext(); } } // 3.改变指向 container = newTable; }
PS.扩容存在的意义:当一个槽里挖得坑太多了,总会有不能再挖的一天,这个时候我们就只能把槽的数量增加,当槽的数量增加之后,我们应该复制之前的所有元素,将其再遍历存一次。
最后的最后,各种数据结构增删查改的时间比较,省略。在下只附上hash表究竟有多快~
相关推荐
哈希表(Hash Table)是一种高效的数据结构
哈希表,数据结构,完整代码,值得学习。C++语言
Search function: This function searches the key specified as the parameter in the hash table. If exist, return true, else return false. Note to use the eq which is a member of HashSet to compare ...
数据结构必做编成题 北京交通大学
严蔚敏数据结构与算法 课本算法实现
自己做的一个哈西表算法,在数据结构实验上能用到,哈西表是进行文件查找的一个非常常用的算法,很重要!
数据结构第16次作业,hash表 Spellchecking Prerequisites, Goals, and Outcomes Prerequisites: Students should have mastered the following prerequisite skills. • Hash Tables - Understanding of the ...
哈希表
白话算法之散列表(Hash Table)从理论到实用.doc
数据结构:⼋⼤数据结构分析 数据结构分类 数据结构是指相互之间存在着⼀种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常⽤的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所...
常用的数据结构有array(数组)、vector(向量)、list(列表)、tree(树)、stack(栈)、queue(队列)、hash table(散列表)、set(集合)、map(映射表)等等。这些数据结构按结构可以分为序列式(sequence)...
TestCuckooHashTable.cpp: Test program for cuckoo hash tables (need to compile CuckooHashTable.cpp also) CaseInsensitiveHashTable.cpp: Case insensitive hash table from STL (Figure 5.23) BinaryHeap.h:...
数据结构常用算法c++实现,程序目录如下: Array shuffle Prime test(trial division) Prime test(Miller-Rabin's method) 2D Array Arbitary Integer Linear congruential generator Maximum subarray problem Bit...
hash table c. stack 6.一个二叉树的三种遍历方法的输出结果 7.链表按升序打印每打印完一个节点就将该节点从链表中删除 8.选择一种算法来整理出一个链接表。你为什么要选择这种方法?现在用o(n)时间来做。 ...
数据结构与算法分析java版 Table of Contents Data Structures and Algorithms in Java - 4 Introduction - 7 Part I Chapter 1 - Overview - 11 Chapter 2 - Arrays - 29 Chapter 3 - Simple Sorting -...
散列表(Hash table):散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。
数组(Array):连续存储元素的集合,可以通过索引访问元素。插入和删除元素的时间复杂度较高,为 O(n),但...哈希表(Hash Table):使用哈希函数将键映射到存储位置的数据结构,可以实现快速的插入、删除和查找操作。
数据结构 构建并使用一个哈希表的简单例子及源程序代码(Dev-c++)