Java学习-Day21

顺序查找与折半查找

一、节点结构

不同于书上的常用整数值来表示所需要存储的内容. 这里使用了键值对的形式来存储. 简而言之就是查找是查找整数表示的键, 返回的是字符串的值.

节点结构和整体初始化代码如下所示:

/**
 * 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

二、顺序查找

1. 描述

简单来说就是从左到右依次遍历然后对比值是否相等, 若相等就返回查找值对对应的内容.

顺序查找使用岗哨可以节约一半的时间. 为此, 第 0 个位置不可以放有意义的数据, 即有效数据只有 length - 1 个.

设置哨岗可以节约时间是因为不需要进行数组越界的判断, 是从减少指令执行的角度来优化代码的.

2. 实现

输入

一个正整数表示需要查找数据的 key.

输出

若查找到对应元素返回对应的字符串

若没找到就返回哨兵位置元素的字符串

时间复杂度

\(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})\)

代码

/**
 *********************
 * 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)\).

二、实现

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

2. 哈希查找

输入

一个正整数表示需要查找数据的 key.

输出

若查找到对应元素返回对应的字符串

若没找到就返回字符串 "null"

时间复杂度

无冲突时为 \(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 成了十六进制.

代码 > Java

#java #eclipse

Java学习-Day22 上一篇

Java学习-Day20 下一篇