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

结果