collections

Performance of List interface implementations

Post Views: 0 LinkedList Performance of get and remove methods is linear time [ Big O Notation is O(n) ] – Performance of add and Iterator.remove methods is constant-time [ Big O Notation is O(1) ] ArrayList The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. [ Big O Notation is O(1) ] – The add operation runs in amortized constant time [ Big O Notation is O(1) ] , but in worst case (since the…

Read More

Performance of Set interface implementations

Post Views: 1 HashSet The HashSet class offers constant-time [ Big O Notation is O(1) ] performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the “capacity” of the backing HashMap instance (the number of buckets). Thus, it’s very important not to set the initial capacity too high…

Read More

Performance of Map interface implementations

Post Views: 1 Hashtable An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a “hash collision”, a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how…

Read More