Morgan Stanley Interview Question
Java DevelopersCountry: India
Interview Type: Phone Interview
Same as the C /C+ it is data structure and it does not change with language.
Storage = O(1) // until no Collision
Retrival= O(1)..
@hprem:
How the storage is O(1) ... I think it would be O(n) because you are mapping a data with some key values. Tell me if i am wrong..
@techDeep It is constant time i.e. O(1). Basically for looking into the key value pair, HashMap uses hashing which gives the precise address location of the 'bucket' which contains the Key.
For example, hashFunction(key)= Memory Location, which you can see is not dependent on n.
PS : it is not as simple as it appears in the example, its just for the sake of simplicity, but the process is essentialy O(1).
@hprem:
Yes i understand but for size of m bucket you need some memory to store location of there buckets . Am i right?
@techieDeep: they mean to say that storing one element takes O(1) time.
Of course storing all the elements will take O(n) space.
All operations on Hashtable or Hashmap are O(1) assuming the uniform distribution of the key in the table and avoiding the collision of the key. Avoiding collision and uniform distribution is all depends how hash function is well implemented which is very critical implementation. But the aim of this data structure is providing operations at O(1).
So if the hash function is really bad than the worst case will be O(N).
HashMap class in java use basically two data structure :
1. Array
2. Link-List.
Therefore on basis of hashing algorithms, if there is no collision happened in hash codes for any data, in that case data will go directly in array, that is why complexity will be O(1).
if collision happens in hash codes then data goes to Link-List , that's mean complexity will be O(n);
Theoretically O(1) if no collisons are there. Worst case O(N) if you override hashcode to return the same value for all objects.
- Abhi January 28, 2013