自定义HashTable存储单词

HashTable存储单词

存储单词的具体原理：将单词中的字母a到z分别对应1到26数字，空格为0进行自定义编码。根据编码规则，将单词中的每一个字母对应到相应的数字。利用幂运算得一个数字。比如:cats所对应的数字为

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");
    }

结果