Hash的简单介绍与java代码实现

这是我在初步接触后，写的关于哈希表的插入、查找、删除、遍历、更改几个基本操作的java代码思路。
哈希表是种数据结构，它可以提供快速的插入操作和查找操作，其余优缺点不加以讨论。但一般的操作必须是根据key值进行。所谓的key值，是唯一标识数据信息的特殊数据，不可重复，如学生的学号，人民的身份证号码。在计算机中，key值可是内存地址，亦可自我设定。下面是关于哈希表的其中一个方式。

在数据就是key值的情况下，将要存放的数据除以某个整数，所得的余数作为放置位置的依据。如上图，设一个哈希表数组中有13个位置，取除数为13，由取余数法知：01数据放置在1号位置，55放置在3号，同时，有时余数可能重复，如14，余数为1，我也将其放置在1号位置，以此类推，可将整数放入一个与其本身有所联系的位置。这就是一种哈希表的简单介绍。
在用java代码实现时，思路是：
key值自我设定，由0开始递增，
在同一个位置只可放置最多三个数据，多的建立下一个数组（一组位置的设定）。
数组间的元素联系采用单向链表，同一个位置的数据亦采用单向链表的方法

先进行一些设置：
public class HashLinkArray {
private int hashLALength = 10;//链表数组的长度
private int hashLALLength = 3;//同一个位置最多可放置的数据个数
｝

因为链表数组是由结点相互联系，它在不同的数组指示我们按一定的顺序进行查找。要先写一个结点类：

public class HashLinkNode {

public  Object[] hlla_Next;//结点数组
public HashLinkNode parent;//父结点
public HashLinkNode child;//子结点
/**
* 设置结点数组
* @param hlla_c 结点数组
*/
public void setHashLinkNode_Array(Object[] hlla_c){
this.hlla_Next=hlla_c;
}
/**
* 得到数组
* @return
*/
public Object[] getHashLinkNode_Array(){
return hlla_Next;
}

}

在用此个结点类中，我们可以开始建立链表数组

public void setHashLinkArray() {
HashLinkNode hln = null;
//第一次建立哈希数组
if (hashLinkArrayNum == 0) {
//哈希数组
Object[] hla = new Object[hashLALength];
hln = new HashLinkNode();
hln.parent = hln;
first_Node = hln;
//设置数组
hln.setHashLinkNode_Array(hla);
hashLinkArrayNum++;

} else {///////非第一次建立/////////////////
hln = first_Node;
while (true) {

if (hln.child != null) {
hln = hln.child;
} else {
HashLinkNode newNode = new HashLinkNode();
newNode.parent = hln;
hln.child = newNode;

Object[] hla = new Object[hashLALength];
newNode.setHashLinkNode_Array(hla);
hashLinkArrayNum++;
break;
}

}

}

}


此前说过，在同一个位置，可最多放置三个数据，这三个数据之间的关系也用单向链表进行表示，再写一个结点类：

public class HashElemNode {
HashElemNode p;//父结点
HashElemNode c;//子结点
int key;//key值
Object newelem;//数据信息
/**
* 得到数据信息
* @return
*/
public Object getElem(){
return newelem;
}

}

增加数据时，首先要计算余数，然后遍历，从第一个数组开始，先得到它的位置，再判断能否放在这个位置，如果不能，再尝试下一个数组，如果没有下一个数组，则建立一个。

/**
* 增加哈希表中的元素
*
* @param newelem
*            新的元素
*/
//key值自定义
public static int key = 0;
public void addHashelem(Object newelem) {
//取余
int lo_key = key % hashLALength;
//首先建立第一个数组
if (hashLinkArrayNum == 0) {
setHashLinkArray();
}
//数据元素的结点
HashElemNode newelemnode = new HashElemNode();
newelemnode.key = key;
newelemnode.newelem = newelem;
//从第一个数组开始遍历
HashLinkNode node = first_Node;
while (true) {
//若此位置没有元素
if (node.getHashLinkNode_Array()[lo_key] == null) {
key++;
node.getHashLinkNode_Array()[lo_key] = newelemnode;
newelemnode.p = newelemnode;
System.out.println("第n组" + hashLinkArrayNum + "key0 is"
+ newelemnode.key + "数据：" + newelemnode.newelem);

break;

} else {
HashElemNode elemnode = (HashElemNode) node
.getHashLinkNode_Array()[lo_key];
if (elemnode.c == null) {//只有一个元素
key++;
newelemnode.p = elemnode;
elemnode.c = newelemnode;
System.out.println("第n组" + hashLinkArrayNum + "key1 is"
+ newelemnode.key + "数据：" + newelemnode.newelem);
break;
} else {//只有两个元素
if (elemnode.c.c == null) {
key++;
newelemnode.p = elemnode.c;
elemnode.c.c = newelemnode;
System.out
.println("第n组" + hashLinkArrayNum + "key2 is"
+ newelemnode.key + "数据："
+ newelemnode.newelem);
break;
} else {
//前面的数组的此位置都满了，建立一个新的数组
if (node.child == null) {
setHashLinkArray();
System.out.println("第n组" + hashLinkArrayNum
+ "======================================");
}
//有三个元素，遍历下一个数组
node = node.child;

}
}
}

}

}



接下来可以进行元素的遍历：

/**
* 遍历哈希表
*/
public int travelHash() {
//从第一个数组开始
HashLinkNode arraynode = first_Node;
int arraynum = 1;//数组个数
int elemnum = 0;//元素个数
while (true) {
for (int i = 0; i < hashLALength; i++) {
//该位置的第一个元素，如果有
if (arraynode.getHashLinkNode_Array()[i] != null) {
HashElemNode elemnode = (HashElemNode) arraynode
.getHashLinkNode_Array()[i];
System.out.println(elemnum + "第" + arraynum + "组" + "key是"
+ elemnode.key + "%后是" + elemnode.key
% hashLALength + "数据是" + elemnode.newelem);
elemnum++;
if (elemnode.c != null) {//第二个
System.out.println(elemnum + "第" + arraynum + "组"
+ "key是" + elemnode.c.key + "%后是"
+ elemnode.c.key % hashLALength + "数据是"
+ elemnode.c.newelem);
elemnum++;

if (elemnode.c.c != null) {//第三个
System.out.println(elemnum + "第" + arraynum + "组"
+ "key是" + elemnode.c.c.key + "%后是"
+ elemnode.c.c.key % hashLALength + "数据是"
+ elemnode.c.c.newelem);
elemnum++;
}

}

}

}

if (arraynode.child != null) {
//遍历下一个数组
arraynode = arraynode.child;
} else {
//退出循环
break;
}

}
return elemnum;

}




通过遍历，我们已经可以找到方法，查到表中每一个元素，删除操作就是把父子结点的更替，或是去掉，只要在遍历的条件上增加key值的判断。查找也是，只需返回这个数据的结点，便可得到数据，不再介绍。