Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 29

Thread: Dictionary using Distributed Hash Table and BST Tree

  1. #1
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Dictionary using Distributed Hash Table and BST Tree

    Hello. I have a problem with my code.
    I have implemented BST Tree as well as DHT but my code doesn't work.
    Here it is:
    import java.util.Scanner;
     
    public class JavaApplication18 
    {
        public static Scanner scan = new Scanner(System.in);
     
        public static void main(String[] args) 
        {
                int n = scan.nextInt();
                DHT dictionary = new DHT(n);
     
                String s = scan.next();
     
                int m = 0;
                while(!"#".equals(s))
                {
                    int p = hash(s, n);
                    dictionary.insert(s, p);
                    m++;
                }
     
                System.out.println(m);
                int k = scan.nextInt();
                String function;
                for(int j = 0; j < k; j++)
                {
                    function = scan.next();
     
                    if(function.charAt(0) == 'S')
                    {
                        String info = s.substring(7);
                        int y = hash(info, n) - 1;
                        System.out.println(info + ": " + dictionary.search(info, y));
                    } else if(function.charAt(0) == 'I') {
                        String info = s.substring(7);
                        int y = hash(info, n) - 1;
                        System.out.println(info + ": " + dictionary.insert(info, y));
                    } else {
                        String info = s.substring(7);
                        int y = hash(info, n) - 1;
                        System.out.println(info + ": " + dictionary.delete(info, y));
                    }
                }
        }
     
        public static class Word
        {
            public String info;
            public Word left;
            public Word right;
            public int hMany;
            public int val;
     
            Word(String value, int k) 
            {
                info = value;
                left = right = null;
                hMany = 1;
                val = k;
            }
        }
     
        public static class BST
        {
            protected Word root;
     
            public BST() 
            {
                root = null;
            }
     
            protected int insert(String x, int k)
            {
                System.out.print("kkk");
                Word s, p = root, prev;
                s = new Word(x, k);
                boolean t = false;
     
                if(root == null)
                {
                    root = s;
                } else {
                    prev = null;
                    while(p != null)
                    {
                        prev = p;
     
                        if(s.val == p.val && x.equals(p.info))
                        {
                            p.hMany++;
                            t = true;
                            break;
                        } else if(s.val < p.val) {
                            p = p.left;
                        } else {
                            p = p.right;
                        }
                    }
     
                    if(t == false && s.val < p.val)
                    {
                        prev.left = s;
                    } else if(t == false) {
                        prev.right = s;
                    }
                }
     
                if(t)
                {
                    return p.hMany;
                } else {
                    return s.hMany;
                }
            }
     
            protected int remove(String x, int t) 
            {
                Word p = root;
                Word ds = null;
                int lp = 0;
     
                while(p != null) // finding parent
                {
                    if(t < p.left.val)
                    {
                        p = p.left;
                    } else if(p.right.val == t && p.right.info.equals(x)) {
                        ds = p.right;
                        lp = 1;
                        break;
                    } else if(p.left.val == t && p.left.info.equals(x)) {
                        ds = p.left;
                        lp = 2;
                        break;
                    } else {
                        p = p.right;
                    }
                }
     
                boolean g = false;
     
                if(ds.hMany > 1) // deleting
                {
                    ds.hMany--;
                } else {
                    g = true;
     
                    if(lp == 2)
                    {   
                        while(true)
                        {
                            if(ds.left == null && ds.right == null)
                            {
                                p.left = null;
                                break;
                            } else if(ds.left != null && ds.right == null) {
                                p.left = ds.left;
                                break;
                            } else if(ds.right != null && ds.left == null) {
                                p.left = ds.right;
                                break;
                            } else {
                                Word temp = ds.right;
     
                                while(temp.left != null && temp.left.left != null)
                                {
                                    temp = temp.left;
                                }
     
                                ds.info = temp.left.info;
                                p = temp;
                                ds = temp.left;
                            }
                        }
                    } else {
                        while(true)
                        {
                            if(ds.left == null && ds.right == null)
                            {
                                p.right = null;
                                break;
                            } else if(ds.left != null && ds.right == null) {
                                p.right = ds.left;
                                break;
                            } else if(ds.right != null && ds.left == null) {
                                p.right = ds.right;
                                break;
                            } else {
                                Word temp = ds.right;
     
                                while(temp.left != null && temp.left.left != null)
                                {
                                    temp = temp.left;
                                }
     
                                ds.info = temp.left.info;
                                p = temp;
                                ds = temp.left;
                            }
                        }
                    }
                }
     
                if(g)
                {
                    return 0 ;
                } else {
                    return ds.hMany;
                }
            }
     
            private int find(String x, int t) 
            {
                Word p = root;
     
                while(p != null && t != p.val)
                {
                    if(t < p.val)
                    {
                        p = p.left;
                    } else if(t == p.val && x.equals(p.info)) {
                        break;
                    } else {
                        p = p.right;
                    }
                }
     
                return p.hMany;
            }
        }
     
        public static class DHT 
        {
            public BST[] bst;
     
            DHT(int n)
            {
                bst = new BST[n];
     
                for(int i = 0; i < n; i++)
                {
                    bst[i] = new BST();
                }
            }
     
            public int insert(String x, int k)
            {
                return bst[k].insert(x, k);
            }
     
            public int search(String x, int k)
            {
                return bst[k].find(x, k);
            }
     
            public int delete(String x, int k)
            {
                return bst[k].remove(x, k);
            }
        }
     
            public static int hash(String key, int l)
            {
                int value = 0;
                int len = key.length() - 1;
     
                for(int j = 0; j < key.length(); j++ ) 
                {
                    value += toDig(key.charAt(j)) * Math.pow(53, len);
                    len--;
                }
     
                value = value % l;
     
                return value;
            }
     
            private static int toDig(char a)
            {
                int value = 0;
                if(Character.isLowerCase(a))
                {
                    value = a - ('a' - 1);
                } else if(Character.isUpperCase(a)) {
                    value = a - ('A' - 27);
                } else if(a == ' ') {
                    value = 53;
                }
                return value;
            }
     
    }

    It takes:
    1. The length of the DHT
    2. Words separated with spaces and finished with #
    3. The number of operations on the dictionary
    4. Operations (SEARCH, DELETE, INSERT)

    While typing:
    7
    a b c d e f g h i j k a a b w # // this is the place where my program crashes
    6
    SEARCH a
    INSERT z
    DELETE a
    SEARCH x
    DELETE b
    DELETE w

    A "wild" exception appears:
    Exception in thread "main" java.lang.NullPointerException
    at javaapplication17.JavaApplication17$DHT.insert(Jav aApplication17.java:249)

    It should return:
    n= 15
    a: 3
    z: 1
    a: 2
    x: 0
    b: 1
    w: 0

    I will appreciate any help.
    Thanks.
    Last edited by dezett; June 22nd, 2012 at 01:20 PM.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Exception in thread "main" java.lang.NullPointerException
    at javaapplication17.JavaApplication17$DHT.insert(Jav aApplication17.java:249)
    Look at line 249 in the code and find which variable has the null value. Then backtrack in the code t see why that variable does not have a valid non-null value.
    If you can't tell what variable is null, add a println before line 249 and print out the values of all the variables used on line 249.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Well, I did as you told me, but it didn't tell me a thing. When I printed the variables i didn't get any null value. They were good. I did the whole function with the arguments given on the paper and it just shouldn't crash. But thx for the help. I am going to sit a bit more and think about it.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Can you post the code that shows what you printed and the statement where the NPE occurs.
    It normally takes a variable with a null value to create a NPE. Did you print ALL of the variables?

    The code you posted has compiler errors in it.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    I have corrected the code. Now it has no compiler errors.
    I have added to the code in main:
    while(!"#".equals(s))
    {
    int p = hash(s, n);
    System.out.println(s + " " + n + " " + p );
    dictionary.insert(s, p);
    m++;
    }

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    That was a big waste of time. Posting code with so many errors.

    Can you explain what the problem with the code is now?

    For testing please put all the answers to the questions the code asks in the Scanner object?
    The idea is to have the program have all the answers in it and then execute the part of the program where the problem is.

    Change the Scanner definition like this:
     Scanner scan = new Scanner("7\na b c d e f g h i j k a a b w #\n <AND REST HERE>");
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    The problem is clearly in the insert method of the BST/DHT class. It crashes at the beginning, while passing the variables from DHT insert to BST insert. It doesn't even print anything when I add a line with a System print out(BST insert).
    Last edited by dezett; June 22nd, 2012 at 11:55 AM.

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    It crashes at the beginning
    Please post the full text of the error message.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Exception in thread "main" java.lang.NullPointerException
    at JavaApplication18$DHT.insert(JavaApplication18.jav a:244)
    at JavaApplication18.main(JavaApplication18.java:18)

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    What variable on line 244 is null? See post#2
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Well, i Can't find such a variable. Though when i was trying to debug, i found that the program has some problems with the DHT constructor. This is what it displayed: Not able to submit breakpoint MethodBreakpoint [JavaApplication18$DHT].DHT '(I)Lvoid;', reason: Method 'DHT' with signature '(I)Lvoid;' does not exist in class JavaApplication18$DHT.

    Maybe i am declaring the table in a bad way?
    Last edited by dezett; June 22nd, 2012 at 12:38 PM.

  12. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    What code is on line 244? What variables are used on that line? Which of those variables is null?

    declaring the table in a bad way
    What variable is the table? Where is it defined?
    If you don't understand my answer, don't ignore it, ask a question.

  13. #13
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    return bst[k].insert(x, k);

    variables: x, k, bst array.
    x = a
    k = n
    bst[1 - n] = null

    line 236
    public static class DHT
    {
    public BST[] bst;

    DHT(int n)
    {
    bst = new BST[n];
    }
    }
    Last edited by dezett; June 22nd, 2012 at 12:45 PM.

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    If bst[k] is null, where do you assign any values to the elements of the bst array?
    There are two steps in using an array of objects:
    1) define the array
    2) fill the array elements with instances of the class
    If you don't understand my answer, don't ignore it, ask a question.

  15. The Following User Says Thank You to Norm For This Useful Post:

    dezett (June 22nd, 2012)

  16. #15
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    I have modified the constructor. Trying to fill the array with the instances.
    DHT(int n)
    {
    bst = new BST[n];

    for(int i = 0; i < n; i++)
    {
    bst[i] = new BST();
    }
    }

    Figured it out.

    Though now my program works badly and gives a line of "k" instead of some results. The 3 methods in BST must be wrong somewhere.
    Last edited by dezett; June 22nd, 2012 at 01:30 PM.

  17. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Make the class static.
    If you don't understand my answer, don't ignore it, ask a question.

  18. The Following User Says Thank You to Norm For This Useful Post:

    dezett (June 22nd, 2012)

  19. #17
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    How should i rehash the words with the same hashcode? Creating another rehash method or using hash again(if hash - how?)?

  20. #18
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Can you explain the problem?
    If you don't understand my answer, don't ignore it, ask a question.

  21. #19
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    I mean: e.g. I get a word with a hashcode 1, so i save it in the BST with the number 1. If i get another word (it's different than the 1st), but it has the same hashcode, I want to save it in the BST 1 again, but to give it a proper position in this tree I need to rehash it, right? So my question is: how can I rehash the word in a proper way? Running the same hash method will give me the same hashcode, so I think it's useless. So how can I do it?

  22. #20
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Are you asking if a word needs a different hashcode for each position it goes to in the container where you are storing it? I don't know the specific algorithm that you are trying to code for to be able to say how it should be done.
    What is the definition of how words are to be stored in the container you are trying to build?
    If you don't understand my answer, don't ignore it, ask a question.

  23. #21
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    I need to use a Hashtable with an independent connecting which will store Binary Search Trees (words are to be stored in an lexicographical order).

  24. #22
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    So the outer layer needs the hash and the inner layer uses the natural lex order?
    If you don't understand my answer, don't ignore it, ask a question.

  25. #23
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    That's right. So in BSTs i should just compare strings? No rehash needed?

  26. #24
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,725
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    Yes, that is what lexical means
    If you don't understand my answer, don't ignore it, ask a question.

  27. #25
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Dictionary using Distributed Hash Table and BST Tree

    I think my hash function has some issue.
    It should give me numbers 1-7 and for "g" it gives me 0.

    public static int hash(String key, int l)
    {
    int value = 0;

    for(int j = 0; j < key.length(); j++ )
    {
    value = (value * 53 + key.charAt(j) - 96);
    }

    value = value % l;

    return value;
    }
    Last edited by dezett; June 23rd, 2012 at 11:02 AM.

Page 1 of 2 12 LastLast

Similar Threads

  1. hash table probes
    By victorh in forum Collections and Generics
    Replies: 4
    Last Post: November 7th, 2011, 11:33 PM
  2. Unscrambler, trying to get the last word of a dictionary...
    By csharp100 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: November 1st, 2011, 03:44 AM
  3. [Jade-Java]Distributed Container
    By ermasto in forum Algorithms & Recursion
    Replies: 0
    Last Post: January 25th, 2011, 05:08 AM
  4. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  5. Find the password with dictionary attack
    By mortis1572 in forum File I/O & Other I/O Streams
    Replies: 1
    Last Post: January 19th, 2010, 09:07 PM

Tags for this Thread