Thread: 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?

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.

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

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)

Originally Posted by Perd1t1on

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).