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.

Results 1 to 5 of 5

Thread: arraylist, hashtable, and 1~2 dimension arrays

  1. #1
    Junior Member
    Join Date
    Jun 2010
    Posts
    26
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default arraylist, hashtable, and 1~2 dimension arrays

    I've always been confused about hashtables/hashmaps. What are they?

    I thought they may be like a 2 dimensional version of an arraylist which is like a 1 dimensional array. If not, what is it, or what are the differences. Most of the descriptions are confusing to me but it just looks like a 2 dimensional array where the indexes are values of differing data types. Would it be used to organize sets of data like you would on a table? And what is a hashset?


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,186
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: arraylist, hashtable, and 1~2 dimension arrays

    Do you understand how "hashing" works. Its a way of reducing the range of a keys to map into a smaller range. And then to allow a very short path for finding a key's value
    For example say your keys could range in values from 1 to 10000. If you had an array of 10000 elements you could store the value for a key using the key as the index to the array. Very fast retrieval of value for key. However, what if you only ever have 100 items stored in that table. That would be a very inefficient use of 9900 empty elements. So hashing.
    If your expect no more that 200 elements to be put into your table and if there were a way to map a key with 10000 different values into a range of numbers from 1 to 200, then you could "hash" the key from 10000 possibilities to 200 possibilities and use that hashed value as the index into a 200 element array to save and restore the value.
    The next level is for collisions, ie when two different keys hash to the same value. Then you need a list at that index to save the values in. Retrieval then at that key requires a short search in the list.

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,267
    Thanks
    176
    Thanked 821 Times in 764 Posts
    Blog Entries
    5

    Default Re: arraylist, hashtable, and 1~2 dimension arrays

    HashMap/Table/Set are a type of java Collection that stores objects quite differently than a list, which makes them advantageous in certain circumstances. It does so by storing object using hashes (eg using an objects hashCode() function - see Norms post above). These can become quite powerful and have quite different uses than an array or list.

    - HashMap/Table allow a key/value relationship. What if you wanted to search several objects by name? You could store the objects as a List or array and iterate over the Array every time you need to find a particular object. However a Map is more suitable for the job. An example could be a dictionary, each entry keyed with the first letter. Here you can quickly look-up a list of words beginning with the a first letter by calling the get method. Map and Table work the same but differ in their synchronization.

    - HashSets store only single instances of objects. This can become useful in circumstances in which you want a set of unique objects.

    One advantage to using the Hash lookup that these objects use is the speed in which the lookup occurs. The following compares the speed to lookup a value in a Set versus a List. Of course this is an extreme, but more than once I've encountered the extreme

    public class Test{
        /**
        *Analyzes the speed of list versus set searches
        */
        public static void main(String[] args){
            final int max = 10000;
            ArrayList<String> list = new ArrayList<String>(max);
            Set<String> set = new HashSet<String>(max);
            //First populate the list and set with identical values
            for ( int i = 0; i < max; i++ ){
                list.add(Integer.toString(i));
                set.add(Integer.toString(i));
            }
            long start = System.currentTimeMillis();
            //search the list max number of times
            for ( int i = 0; i < max; i++ ){
                int num = (int)(Math.random() * max);
                list.indexOf(Integer.toString(num));
     
            }
            System.out.print("Time to search list: ");
            System.out.println(System.currentTimeMillis() - start);
            start = System.currentTimeMillis();
            //search the set max number of times
            for ( int i = 0; i < max; i++ ){
                int num = (int)(Math.random() * max);
                set.contains(Integer.toString(num));
            }
            System.out.print("Time to search set: ");
            System.out.println(System.currentTimeMillis() - start);
        }
    }

    List, Map, and Set...each has their use and whenever a Collection is used one should consider which Collection is the most appropriate for the job at hand

  4. #4
    Junior Member
    Join Date
    Jun 2010
    Posts
    26
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: arraylist, hashtable, and 1~2 dimension arrays

    thanks, after playing around with it I realized that a hashset can only add members and check if a member is inside the hashset. So it's limited but fast. I'm guessing you would convert it to an array after you have established what it contains as opposed to making an array that could have empty elements. It's advantage over a list is that it is much faster, but cannot retrieve indexes. Is this all right?

    Also, I wondered about the portion of your code where you check if list has an index of(num) compared to checking if the set contains (num), and thought it would be obviously be faster because one returns an int, while the other returns a boolean, but then I changed the indexOf method to a cantains method and got the same output. (~1260ms to ~10ms)

  5. #5
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,267
    Thanks
    176
    Thanked 821 Times in 764 Posts
    Blog Entries
    5

    Default Re: arraylist, hashtable, and 1~2 dimension arrays

    Quote Originally Posted by Perd1t1on View Post
    thanks, after playing around with it I realized that a hashset can only add members and check if a member is inside the hashset. So it's limited but fast. I'm guessing you would convert it to an array after you have established what it contains as opposed to making an array that could have empty elements. It's advantage over a list is that it is much faster, but cannot retrieve indexes. Is this all right?
    You can iterate over the set by retrieving its iterator:
     
    Set<String> mySet = new HashSet<String>();
    ....
     
    Iterator<String> it = mySet.iterator():
    while (it.hasNext()){
        String s = it.next();
    }
    However based upon how the storage works, the order is not guaranteed - eg don't expect this method to iterate over the contents in the order the objects were placed in the set (a LinkedHashSet can accomplish this however).

Similar Threads

  1. How to use an ArrayList and what is its advantage over array?
    By JavaPF in forum Java SE API Tutorials
    Replies: 4
    Last Post: December 21st, 2011, 03:44 AM
  2. Multi-dimension ArrayList example
    By adeola in forum Collections and Generics
    Replies: 3
    Last Post: March 26th, 2010, 03:23 AM
  3. Multi-dimension ArrayList example
    By helloworld922 in forum Java Programming Tutorials
    Replies: 1
    Last Post: February 3rd, 2010, 10:01 AM
  4. [SOLVED] Hashtable and Key Size
    By sapzero in forum Collections and Generics
    Replies: 0
    Last Post: January 28th, 2010, 01:31 PM
  5. slicer dimension in MDX
    By retail_deepa in forum Java Servlet
    Replies: 3
    Last Post: August 28th, 2009, 04:01 AM