hash简易表

 

哈希表是结合数组跟链表的算法，可以说哈希表是一个装有链表的数组，他继承了数组易查找，链表易插入，删除的特点。

 

 

现假设有若干（0-99）学生，他们的学号从0-99中的随机整数，现在要将同学的学号放到哈希表中，并能通过学号得到对应的姓名。并能够进行查找，删除，插入。

则该表储存数据的形式如下所示。

插入值：将id除以10，得到的结果就是该元素数组索引号，如果该位置下还没有值，就将该值直接放入，如果该位置已有值就将该值放在最后一个元素的后面。相当与挂链。

查找,删除值：通过上面的方法，定位到某元素，然后对该元素进行操作。

rehash问题：因为这里的分组已经固定了，而学生也有限制，所以没必要rehash。

  该程序程序包含的主要功能函数有：

 

search( )：在哈希表中查找关键字

Insert( )：向哈希表中插入关键字

remove( )：删除哈希表中某一关键字

showAll( )：打印输出哈希表  

这里其实算不上完整的hash，认为是对已知的学号进行处理，所以可以事先确定数组的长度，就省去了rehash，还有这里的hash算法也很简单（学号除以10）

 

 

package Text;

import java.util.ArrayList;
import java.util.List;

import cn.netjava.hash.Node;

public class HashTable {
	private ArrayList array[];// 定义一个存放链表的数组
	private int arraySize;// 数组的长度
	private int mem = 0;// 链表中的元素个数

	// 有参构造器
	public HashTable(int size) {
		this.arraySize = size;
		this.array = new ArrayList[arraySize];

		for (int i = 0; i < size; i++) {// 创建一个有size个元素的数组
			ArrayList<Integer> list = new ArrayList();// 新建一个装有整数的链表
			this.array[i] = list;// 将链表放入数组
		}
	}
	public boolean ifHave(ArrayList<Integer> aList, int id) {
		for (int i = 0; i < aList.size(); i++) {
			aList.get(i);
			if (id == aList.get(i)) {
				return true;// 该链表中已有id值
			}
		}
		return false;
	}
	public void addMem(int id) {
		int index = id / 10;// 得到数组下标
		ArrayList aList = array[index];// 得到数组中该元素中的链表
		if (ifHave(aList, id)) {// 如果已经有该数据，则返回
			System.out.println("该数据已经添加，请勿重复");
		} else {// 如果没有该数据
			System.out.println("成功添加数据");
			aList.add(id);// 将该链表添加到数组中
		}
	}
	// 移除某元素
	public void remove(int id) {
		int index = id / 10;// 得到数组下标
		ArrayList aList = array[index];// 得到数组中该元素中的链表
		if (ifHave(aList, id)) {// 如果有该数据，则删除
			for (int i = 0; i < aList.size(); i++) {
				if (aList.get(i).equals(id)) {
					aList.remove(i);
					System.out.println("成功删除该元素");
				}
			}
		} else {// 没有就返回
			System.out.println("指定的元素不存在");
		}
	}
	// // 取得其中的一个数
	public void search(int id) {
		int index = id / 10;
		ArrayList aList = array[index];// 得到数组中该元素中的链表
	}

	public void showAll() {
		for (int i = 0; i < arraySize; i++) {
			ArrayList<Integer> list = array[i];
			for (int j = 0; j < list.size(); j++) {
				System.out.println("位于第"+i+"组，是第"+j+"号："+list.get(j));
			}
		}
	}
	public static void main(String args[]) {//测试函数
		HashTable ht = new HashTable(9);
		ht.addMem(49);
		ht.showAll();
	}
}