自定義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<hashArraySize;i++){
            hashArray[i]=new SingleLinkedList();
        }
    }
    public void displayHashTable(){
        for(int i=0;i<hashArraySize;i++){
            System.out.print(i+":");//display cell number
            hashArray[i].displaySingleLinkedList(); //display list
        }
    }

    /**
     *      * Alphabetical code table
     *      * 0        1     2     3    4    5    6     7     8     9    10       11     12   13  14   15      16   17   18       19    20     21     22    23    24   25    26
     *      * 空格    a     b    c     d    e    f     g      h    i      j       k     l      m   n    o      p    q     r       s     t       u     v     w     x     y    z
     * @param letter
     * @return
     */
    public int getLetterCode(char letter){
        int letterCode = 0;
        switch (letter){
            case 'a':
                letterCode = 1;
                break;
            case 'b':
                letterCode = 2;
                break;
            case 'c':
                letterCode = 3;
                break;
            case 'd':
                letterCode = 4;
                break;
            case 'e':
                letterCode = 5;
                break;
            case 'f':
                letterCode = 6;
                break;
            case 'g':
                letterCode = 7;
                break;
            case 'h':
                letterCode = 8;
                break;
            case 'i':
                letterCode = 9;
                break;
            case 'j':
                letterCode = 10;
                break;
            case 'k':
                letterCode = 11;
                break;
            case 'l':
                letterCode = 12;
                break;
            case 'm':
                letterCode = 13;
                break;
            case 'n':
                letterCode = 14;
                break;
            case 'o':
                letterCode = 15;
                break;
            case 'p':
                letterCode = 16;
                break;
            case 'q':
                letterCode = 17;
                break;
            case 'r':
                letterCode = 18;
                break;
            case 's':
                letterCode = 19;
                break;
            case 't':
                letterCode = 20;
                break;
            case 'u':
                letterCode = 21;
                break;
            case 'v':
                letterCode = 22;
                break;
            case 'w':
                letterCode = 23;
                break;
            case 'x':
                letterCode = 24;
                break;
            case 'y':
                letterCode = 25;
                break;
            case 'z':
                letterCode = 26;
                break;
        }
        return letterCode;
    }
    /**
     * get hash code of word
     * @param word
     * @return
     */
    public int hashFuc(String word){
        long  oldScope =0;
        int  newScope ;
        int wordLength = word.length();
        for(int i=wordLength-1,j=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");
    }

結果