学习来源：日撸 Java 三百行（41-50天，查找与排序）_闵帆的博客-CSDN博客
- 顺序查找与折半查找
- 一、节点结构
- 二、顺序查找
- 1. 描述
- 2. 实现
- 输入
- 输出
- 时间复杂度
- 代码
- 运行截图
- 小提示
- 三、折半查找
- 1. 描述
- 2. 实现
- 输入
- 输出
- 时间复杂度
- 代码
- 运行截图
- 哈希表
- 一、描述
- 二、实现
- 1. 初始化哈希表
- 输入
- 输出
- 代码
- 2. 哈希查找
- 输入
- 输出
- 时间复杂度
- 代码
- 运行截图
- 总结
不同于书上的常用整数值来表示所需要存储的内容. 这里使用了键值对的形式来存储. 简而言之就是查找是查找整数表示的键, 返回的是字符串的值.
节点结构和整体初始化代码如下所示:
/**
* An inner class for data nodes. The text book usually use an int value to
* represent the data. I would like to use a key-value pair instead.
*/
class DataNode {
/**
* The key.
*/
int key;
/**
* The data content.
*/
String content;
/**
*********************
* The first constructor.
*********************
*/
DataNode(int paraKey, String paraContent) {
key = paraKey;
content = paraContent;
}// Of the second constructor
/**
*********************
* Overrides the method claimed in Object, the superclass of any class.
*********************
*/
public String toString() {
return "(" + key + ", " + content + ") ";
}// Of toString
}// Of class DataNode
/**
* The data array.
*/
DataNode[] data;
/**
* The length of the data array.
*/
int length;
/**
*********************
* The first constructor.
*
* @param paraKeyArray The array of the keys.
* @param paraContentArray The array of contents.
*********************
*/
public DataArray(int[] paraKeyArray, String[] paraContentArray) {
length = paraKeyArray.length;
data = new DataNode[length];
for (int i = 0; i < length; i++) {
data[i] = new DataNode(paraKeyArray[i], paraContentArray[i]);
} // Of for i
}// Of the first constructor
/**
*********************
* Overrides the method claimed in Object, the superclass of any class.
*********************
*/
public String toString() {
String resultString = "I am a data array with " + length + " items.\r\n";
for (int i = 0; i < length; i++) {
resultString += data[i] + " ";
} // Of for i
return resultString;
}// Of toString
简单来说就是从左到右依次遍历然后对比值是否相等, 若相等就返回查找值对对应的内容.
顺序查找使用岗哨可以节约一半的时间. 为此, 第 0 个位置不可以放有意义的数据, 即有效数据只有 length - 1 个.
设置哨岗可以节约时间是因为不需要进行数组越界的判断, 是从减少指令执行的角度来优化代码的.
2. 实现 输入一个正整数表示需要查找数据的 key.
输出若查找到对应元素返回对应的字符串
若没找到就返回哨兵位置元素的字符串
时间复杂度O ( n ) O(n) O(n)
代码 /**
*********************
* Sequential search. Attention: It is assume that the index 0 is NOT used.
*
* @param paraKey The given key.
* @return The content of the key.
*********************
*/
public String sequentialSearch(int paraKey) {
data[0].key = paraKey;
int i;
// Note that we do not judge i >= 0 since data[0].key = paraKey.
// In this way the runtime is saved about 1/2.
// This for statement is equivalent to
// for (i = length - 1; data[i].key != paraKey; i--);
for (i = length - 1; data[i].key != paraKey; i--) {
;
} // Of for i
return data[i].content;
}// Of sequentialSearch
/**
*********************
* Test the method.
*********************
*/
public static void sequentialSearchTest() {
int[] tempUnsortedKeys = { -1, 5, 3, 6, 10, 7, 1, 9 };
String[] tempContents = { "null", "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);
System.out.println(tempDataArray);
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(10));
System.out.println("Search result of 5 is: " + tempDataArray.sequentialSearch(5));
System.out.println("Search result of 4 is: " + tempDataArray.sequentialSearch(4));
}// Of sequentialSearchTest
虽然在代码中存在 {key:-1 , value:“null”} 这一个数据. 但是这是人为表示找不到时应该返回的元素. 那么输入的就应该是为正整数.
三、折半查找 1. 描述折半查找只能适用于单调递增或者单调递减的顺序表中. 正是因为这个严格的限制才能有折半查找这个方法.顾名思义就是每次查找要舍去一半的数据.
但是这个又会出现一个新的问题, 要是所有元素都一样呢？ 虽然这不会影响查找到的数据, 在一般的算法题中要求返回第一次出现的下标就不能确定了. 解决办法自然是有的这里就不细说了.
2. 实现 输入一个正整数表示需要查找数据的 key.
输出若查找到对应元素返回对应的字符串
若没找到就返回字符串 “null”
时间复杂度O ( log n ) O(\log{n}) O(logn)
代码 /**
*********************
* Binary search. Attention: It is assume that keys are sorted in ascending
* order.
*
* @param paraKey The given key.
* @return The content of the key.
*********************
*/
public String binarySearch(int paraKey) {
int tempLeft = 0;
int tempRight = length - 1;
int tempMiddle = (tempLeft + tempRight) / 2;
while (tempLeft <= tempRight) {
tempMiddle = (tempLeft + tempRight) / 2;
if (data[tempMiddle].key == paraKey) {
return data[tempMiddle].content;
} else if (data[tempMiddle].key <= paraKey) {
tempLeft = tempMiddle + 1;
} else {
tempRight = tempMiddle - 1;
}
} // Of while
// Not found.
return "null";
}// Of binarySearch
/**
*********************
* Test the method.
*********************
*/
public static void binarySearchTest() {
int[] tempSortedKeys = { 1, 3, 5, 6, 7, 9, 10 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempSortedKeys, tempContents);
System.out.println(tempDataArray);
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(10));
System.out.println("Search result of 5 is: " + tempDataArray.binarySearch(5));
System.out.println("Search result of 4 is: " + tempDataArray.binarySearch(4));
}// Of binarySearchTest
哈希表是根据关键码值(Key value)而直接进行访问的数据结构. 也就是说, 它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度. 这个映射函数叫做哈希函数, 存放记录的数组叫做哈希表.
在构造方法中装入数据. 规定了所有数据的个数保证每个数都有能够被存储. 那么这个数组就叫做散列表.
使用 (最简单的) 除数取余法获得数据存放地址 (下标), 使用 (最简单的) 顺移位置法解决冲突. 这个就是哈希函数.
搜索的时间复杂度仅与冲突概率相关, 间接地就与装填因子相关. 如果空间很多, 可以看出时间复杂度为 O ( 1 ) O(1) O(1).
二、实现 1. 初始化哈希表 输入key数组、存储内容数组和 哈希表的长度(必须要大于等于 key 数组的长度)
输出无
代码 /**
*********************
* The second constructor. For Hash code only. It is assumed that
* paraKeyArray.length <= paraLength.
*
* @param paraKeyArray The array of the keys.
* @param paraContentArray The array of contents.
* @param paraLength The space for the Hash table.
*********************
*/
public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) {
// Step 1. Initialize.
length = paraLength;
data = new DataNode[length];
for (int i = 0; i < length; i++) {
data[i] = null;
} // Of for i
// Step 2. Fill the data.
int tempPosition;
for (int i = 0; i < paraKeyArray.length; i++) {
// Hash.
tempPosition = paraKeyArray[i] % paraLength;
// Find an empty position
while (data[tempPosition] != null) {
tempPosition = (tempPosition + 1) % paraLength;
System.out.println("Collision, move forward for key " + paraKeyArray[i]);
} // Of while
data[tempPosition] = new DataNode(paraKeyArray[i], paraContentArray[i]);
} // Of for i
}// Of the second constructor
一个正整数表示需要查找数据的 key.
输出若查找到对应元素返回对应的字符串
若没找到就返回字符串 “null”
时间复杂度无冲突时为 O ( 1 ) O(1) O(1)
代码 /**
*********************
* Hash search.
*
* @param paraKey The given key.
* @return The content of the key.
*********************
*/
public String hashSearch(int paraKey) {
int tempPosition = paraKey % length;
while (data[tempPosition] != null) {
if (data[tempPosition].key == paraKey) {
return data[tempPosition].content;
} // Of if
System.out.println("Not this one for " + paraKey);
tempPosition = (tempPosition + 1) % length;
} // Of while
return "null";
}// Of hashSearch
/**
*********************
* Test the method.
*********************
*/
public static void hashSearchTest() {
int[] tempUnsortedKeys = { 16, 33, 38, 69, 57, 95, 86 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents, 19);
System.out.println(tempDataArray);
System.out.println("Search result of 95 is: " + tempDataArray.hashSearch(95));
System.out.println("Search result of 38 is: " + tempDataArray.hashSearch(38));
System.out.println("Search result of 57 is: " + tempDataArray.hashSearch(57));
System.out.println("Search result of 4 is: " + tempDataArray.hashSearch(4));
}// Of hashSearchTest
顺序查找是经常使用的但是没有考虑哨兵. 可能没有接触过上千万或者上亿的数据, 对时间的要求还是不太敏感. 哈希表我最能想到的就是诸多账号的存储, 像 QQ 的账号就被 Hash 成了十六进制.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）