0

So I am creating a Hash Table that uses an Array of Linked Lists of Arrays. Let me take a second to explain why this is.

So I have previously implemented Hash Tables by creating an Array, and each element of the array is a Linked List. This way I could quickly look up a LL of 450,000 elements by searching for the hash value first in the array, and searching the elements of this LL. I should add that this is a project for school and I cannot just use the Hash Tables that comes with java.

Now I want to do something similar... but I massive have a LL of Arrays that I need to search. Here each element of the LL is line of a text file, which represented by a 4 element array, where each of the 4 elements is a different string that was tab delimited in the input file. I need to be able to quickly access the 2nd, 3rd, and 4th string that was located in each line, and that is now an element of this array.

So What I want is to be able to create an Array of LL of Arrays... first I will find the sum of the ascii values of the second element of an array. Then I will hash the entire array using this value into by Hash Table. Then when I later need to find this element, I will go to the corresponding element of the array, where I have a list of arrays. I will the search for the 2nd value of each array in the list. If i find the one I want, then I return that array, and use the 3rd and 4th element of this array.

As I said, I have this working fine for an Array of LL, but adding the extra dimension of Arrays inside has thrown me off completely. I think it is mostly just figuring out syntax, since I have successfully initialized a Array of LL of Arrays (public static LinkedList[] RdHashLL) so it appears that Java is okay with this in principal. However, I have no idea how to put elements into the Hash Table, and how to read them out.

Below is my code for a ARRAY OF LINKED LISTS that works FINE. I just need help getting it to work for an ARRAY OF LL OF ARRAYS!

public class TableOfHash{

public static LinkedList<String>[] HashLL;

//HASH FUNCTION - Finds sum of ascii values for string
public static int charSum(String s){
    int hashVal = 0;
    int size = 1019; //Prime Number around size of 8 char of 'z', (8 chars is amoung largest consistantly in dictionary)

    for(int i = 0; i < s.length(); i++){
        hashVal += s.charAt(i);
    }   
    return hashVal % size;
}

//CREATE EMPTY HASH TABLE - Creates an array of LL
public static void makeHash(){
    HashLL = new LinkedList[1019];
    for(int i=0; i<HashLL.length; i++){
        HashLL[i] = new LinkedList<String>();
    }
}

//HASH VALUES INTO TABLE!
public static void dictionary2Hash(LinkedList<String> Dict){
    for(String s : Dict){
        HashLL[charSum(s)].add(s);
        //Finds sum of char vales of dictionary element i,
        //and then word at i to the HashLL at point defined
        //by the char sum.
    }   
    //Print out part of Hash Table (for testing! for SCIENCE!)
    //System.out.println("HASH TABLE::");
    //printHashTab();
}

//SEARCH HashTable for input word, return true if found
public boolean isWord(String s){

    if(HashLL[charSum(s)].contains(s)){
        wordsfound++;
        return true;
    }
    return false;
}

}

I have made some attempts to change this, but for things like if(HashLL[charSum(s)].contains(s)) which searches the LL at the element returned by charsum(s)... I have no idea how to get it to work when it is a LL of Arrays and not of Strings. I have tired HashLL[charSum(s)].[1].contains(s)), and HashLL[charSum(s)][1].contains(s)), and various other things.

The fact that a Google search for "Array of Linked Lists of Arrays" (with quotes) turns up empty has not helped.

Last bit. I realize there might be another data structure that would do what I want, but unless you believe that a Array of LL of Arrays is a totally hopeless cause, I'd like to get it to work as is.

3
  • are you looking for LinkedList<String[]>[] hashLL; ? Commented Nov 22, 2012 at 18:09
  • You could use google guava library for this kind of datastructure Commented Nov 22, 2012 at 18:11
  • I can initialize it fine as public static LinkedList<String[]>[] RdHashLL, but getting it to functionally work with adding values and searching values I cannot get to work. Commented Nov 22, 2012 at 18:12

1 Answer 1

1

if you have

LinkedList<String[]>[] hashLL;

you can read a specific String like this (one of many ways)

String str = hashLL[outerArrayIndex].get(listIndex)[innerArrayIndex];

To write into the fields, this is possible (assuming everything is initialized correctly).

String[] arr = hashLL[outerArrayIndex].get(listIndex);
arr[index] = "value";
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks! This worked (with some minor changes for what I needed to do). Thanks a lot!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.