Java: internal data structure in Map

Question

I am trying to create a class that implements the Map interface. So I am writing code that will check if the caller is empty or not. However, I got a little confused about which data structure I should use domestically. I am currently using a Hash Table. thanks in advance

Answer 1

From Wikipedia ,

Associative arrays are usually used when the search is most common operation. For this reason, implementations are usually designed to provide quick searches, due to slower insertion and more storage than other data structures (such as association lists).

Effective performance:
There are two main effective data structures used to represent associative arrays, a hash table and a self-balancing binary search tree (for example, red-black tree or AVL tree). Skip lists are also alternative, although relatively new and not so widely used. B-trees (and variants) can also be used and is usually used when the associative array is too large to be completely in memory, for example, in a simple database. Relative advantages and disadvantages include:

• Asymptotic performance: hash tables have faster average search and insertion time, O (1), compared to balanced binary search tree Θ (log n), while balanced trees are faster than worst search and insertion time, O (log n) compared to Θ (n). O (n) worst case and O (log n) average run times, but with less insertion and deletion overhead in practice than balanced binary trees, skip lists.

• Saving orders: balanced binary trees and skip lists keep ordering - allowing you to efficiently iterate through the keys in order or to efficiently find a relationship whose key is close to a given value. Hash tables do not preserve order and therefore cannot perform these operations as efficiently (they require sorting the data in a separate step).

• Range requests: balanced binary trees can be easily adapted to efficiently assign a single value to a large ordered range of keys or count the number of keys in an ordered assortment. (With n elements in the array and performing an operation on an adjacent range of m keys, a balanced binary tree will take the time O (log (n) + m) while the hash table should have the value Θ (n) the time needed to find everything table).

• Distribution behavior: hash tables with open addressing store all data in a large contiguous block of memory that is reallocated infrequently, while tree allocation makes many small, frequent allocations. As hash tables of results can be difficult to allocate a fragmented heap and vice versa, trees can cause heap fragmentation. Trees are also more vulnerable to inefficiencies in spreaders.

• Compactness: hash tables can have a more compact storage for small type values, especially when bit values.

• Persistence: There are simple, constant versions of balanced binary trees that are especially noticeable in functional languages.

• Support for new types of keys. Creating a hash table requires a reasonable hash function for the key type, which can be difficult to write well, while balanced binary trees and skip lists only require a complete ordering of the keys.

Sometimes simple implementations have one data structure or another flaw that a better design can overcome. For instance:

• Hash tables that use untrusted input as keys can be vulnerable to denial of service attacks when untrusted user data intended to generate a large amount of collision. This can be overcome by randomly selecting hash functions from a universal family or hashing insecure input with cryptographic hash functions before insertion.

• Simple balanced trees lose space on pointers and metadata distribution; these problems can be mitigated by storing multiple elements in each node and using memory pools.

Answer 2

In addition to the table itself, you can also maintain an integer member variable to track the size of the collection, increasing it every time with every new match and decreasing every time it is deleted. Thus, you can simplify the interface methods size and isEmpty :

 public int size() { return this.size; } public boolean isEmpty() { return this.size == 0; } 

Answer 3

I tried different methods, but ended up expanding some data structures that were so strong that I didn't need coding skills. So I decided to use regular string arrays (2) from a virtual hash map, such as a structure that expanded as space expanded.

Below is a link to the full code.

http://code.google.com/p/rohan-oopconcept-assignment/source/browse/trunk/src/EmployeeMap.java