自定义HashTable存储单词
HashTable存储单词
存储单词的具体原理:将单词中的字母a到z分别对应1到26数字,空格为0进行自定义编码。根据编码规则,将单词中的每一个字母对应到相应的数字。利用幂运算得一个数字。比如:cats所对应的数字为
10多年专注成都网站制作,企业网站制作,个人网站制作服务,为大家分享网站制作知识、方案,网站设计流程、步骤,成功服务上千家企业。为您提供网站建设,网站制作,网页设计及定制高端网站建设服务,专注于企业网站制作,高端网页制作,对成都餐厅设计等多个行业,拥有丰富的网站运维经验。
3*27^3+1*27^2+20*27^1+19*27^0=60337
这样得到了一个数值,如果将该值作为数组下标,10个字母的单词就有可能超过7000000000000,数字过于庞大,所以要压缩。为了方便显示,所以我将哈希表的长度设为10,即压缩到0到9范围内。但是又由于long类型范围的限制,最多只能存放长度为7个字母的单词。
下面是源代码
自定义链表节点
/**
* define single link list node class
*/
public class LinkedNode {
String dataItem;
LinkedNode next;
public LinkedNode(String data){
this.dataItem = data;
}
public String getNodeData(){
return dataItem;
}
}
自定义单向链表
/**
* define Link List class
*/
public class SingleLinkedList {
private LinkedNode first;
private LinkedNode last;
int size;
//Constructor
public SingleLinkedList(){
first = null;
last = null;
size = 0;
}
public void insert(LinkedNode linkedNode){
if(first==null){
first = linkedNode;
}
else {
LinkedNode l = last;
l.next = linkedNode;
}
last = linkedNode;
size++;
}
public boolean searchSingleLink(String data){
LinkedNode i = null;
for(i =first;i!=null;i=i.next){
if(i.dataItem.equals(data)){
return true;
}
}
if(i==null){
return false;
}
return false;
}
public void displaySingleLinkedList(){
for(LinkedNode i = first;i!=null;i=i.next){
System.out.print(i.getNodeData()+"->");
}
System.out.println("null");
}
@Test
public void SingleLinkedTest() {
SingleLinkedList singleLinkedList = new SingleLinkedList();
LinkedNode linkedNode = new LinkedNode("a");
singleLinkedList.insert(linkedNode);
LinkedNode linkedNode1 = new LinkedNode("b");
singleLinkedList.insert(linkedNode1);
singleLinkedList.displaySingleLinkedList();
}
}
自定义hash表
public class MyHashTable {
int hashArraySize;
SingleLinkedList[] hashArray;
public MyHashTable(int capacity){
hashArraySize = capacity;
hashArray = new SingleLinkedList[hashArraySize];
for(int i = 0;i=0;i--,j++){
int letterCode = getLetterCode(word.charAt(i));
oldScope += letterCode* Math.pow(27,j );
}
newScope = (int)oldScope%10;
return newScope;
}
public void insertIntoHashArray(String word){
LinkedNode linkedNode = new LinkedNode(word);
int arrayIndex = hashFuc(word);
hashArray[arrayIndex].insert(linkedNode);
}
public void findWord(String word){
int index = hashFuc(word);
boolean b = hashArray[index].searchSingleLink(word);
if(b){
System.out.println(word+"在hashTable中存在");
}else {
System.out.println(word+"在hashTable中不存在");
}
}
}
测试
public static void main(String[] args) {
MyHashTable myHashTable = new MyHashTable(10);
myHashTable.insertIntoHashArray("cats");
myHashTable.insertIntoHashArray("apple");
myHashTable.insertIntoHashArray("and");
myHashTable.insertIntoHashArray("a");
myHashTable.insertIntoHashArray("or");
myHashTable.insertIntoHashArray("contact");
myHashTable.displayHashTable();
myHashTable.findWord("a");
myHashTable.findWord("b");
}
结果
新闻标题:自定义HashTable存储单词
分享URL:http://myzitong.com/article/pjchsj.html