3

I've been researching to find a faster alternative to list. In an algorithm book, hashtable seems to be the fastest using separate chaining. Then I found that java has an implementation of hashtable and from what I read it seems to it uses separate chaining. However, there is the overhead of synchronization so the implementation of hashmap is suggested as a faster alternative to hashtable.

My queations are:

  • Is java hashmap the fastest data structure implemented in java to insert/delete/search?
  • While reading, a few posts had concerns about the memory usage of hashmap. One post mentioned that an empty hashmap occupy 300 bytes. Is hashtable more memory efficient than hasmap?
  • Also, is the hash function in each the most efficient for strings?
Bosko Mijin
  • 3,287
  • 3
  • 32
  • 45
WhatIf
  • 653
  • 2
  • 8
  • 18
  • 4
    If any one data structure was most efficient for all cases, then there wouldn't be need to any other data structure at all. Now please explain your scenario. – Rohit Jain Jan 13 '14 at 18:17
  • i think it depends on the data type you are using and the expected scenarios. can you please explain about the needs of your app? btw, you can set the initial capacity of the hashMap instead of using the default one. – android developer Jan 13 '14 at 18:18
  • A hash table can be 'empty', but would still require the basic array that goes with it - the size of this array depends on how large you make your hash table. – Bernhard Barker Jan 13 '14 at 18:48

6 Answers6

1

There is too much context missing to be able to answer the question which suggests to me that you should use the simplest option and not worry about performance until you have measured that you have a problem.

Is java hashmap the fastest data structure implemented in java to insert/delete/search?

ArrayList is significantly faster than HashMap depending on that you need it for. I have seen people use Maps when they should have used objects. In this case a custom class instance can be 10 faster and smaller.

While reading, a few posts had concerns about the memory usage of hashmap. One post mentioned that an empty hashmap occupy 300 bytes.

Unless you know that 300 bytes (which costs less than what you would be paid on minimum wage to blink) matters, I would assume it doesn't.

Is hashtable more memory efficient than hasmap?

It can be but not enough to matter. Hashtable starts with a smaller size by default. If you make a HashMap with a smaller capacity it will be smaller.

Also, is the hash function in each the most efficient for strings?

In the general case it is efficient enough. In rare cases you may want to change the strategy eg to prevent denial of service attacks. If you really care about memory efficiency and performance perhaps you shouldn't be using String in the first place.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
0

HashMap (or, more likely, HashSet) is probably a good place to start, at your point. It's not perfect, and it does consume more memory than e.g. a list, but it should be your default when you need fast add, remove, and contains operations. The String.hashCode() implementation is not the best hash function, though it is fast, and good enough for most purposes.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
0

As you've pointed Hashtable is fully synchronized so it depends on your environment. IF you have many threads then ConcurrentHashMap will be better solution. However you can look at Trove4J - maybe it will better suite your needs. Trove uses chaining hashing similar to hashtables

Jakub Kubrynski
  • 13,724
  • 6
  • 60
  • 85
0

The access time of HashMap (& HashTable as well I believe) is O(1) since the internal bucket placement of the given value during put() is determined by computing (Hash of the value's key) % (Total Number of buckets). This O(1) is average access time, if however many keys hash to the same bucket then the access time will tend towards O(n) as all the values are placed into the same bucket grow and they all grow in linked list fashion.

As you said considering the overhead of synchronization inside Hashtable, I would probably opt for Hash map. Besides you can fine tune Hashmap by setting its various params like load factor that offers means of memory optimization. I vote for HashMap...

Ace
  • 1,501
  • 4
  • 30
  • 49
0

As others pointed out, a set would be a good replacement for a list but don't forget that lists allow duplicate elements, while sets do not, so while certain operations are faster, e.g., exists, sets and lists represent solutions to different problems.

As a start I recommend HashSet or TreeSet (in case ordering is important). A HashMap maps keys to values which is different. Refer to this discussion to understand the differences between the HashMap and Hashtable. I personally haven't used a Hashtable since 2007.

Finally, if you don't mind using a third party library, I highly recommend to take a look at the Guava immutable collections. Immutability automatically provides thread safety and easier to understand programs.

EDIT: Regarding efficiency concerns, this is a moot point. As a guideline, use the data structure (as in the abstract concept of a data structure) that best fits your problem and choose the vanilla implementation available. If you can prove you have a performance problem in you code, you might start thinking about using something 'more efficient'. That's in quote because it's a very loose definition: are we talking about memory efficiency, computing time efficiency, garbage collection efficiency, etc. Never forget the rules for code optimization.

Community
  • 1
  • 1
Giovanni Botta
  • 9,626
  • 5
  • 51
  • 94
0

1.HashMap is only one of the fastest data structures implemented in java to insert/delete/search，HashSet is as fast as HashMap to insert/delete/search,and ArrayList is as fast as HashMap when insert a element to the end.

2.Hashtable is not more memory efficient than HashMap,they are all implemented by separate chaining.

3.Hash function of the two data structures are the same,but you can write a subclass extends them then override the hash function to make it most fit your application.

xinghui
  • 22
  • 3