• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

collections

 
Ranch Hand
Posts: 84
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Both linkedlist and Arraylist extend the List interface. How are they different from each other and from the practical point of view when youd you use each of them ?
Similarly both HashMap and HashTable extend the Map interface. what is the difference between HashMap and HashTable ? Under what circumstances would you use each of them ?
Where does Hashset come into the picture?
Thanks
 
Ranch Hand
Posts: 203
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I fyou want to insert large number of elements in the middle of the collection then you go for LinkedList. If the addtion is at the end of the collection ArrayList is preferable.
ArrayList and Vector implement Random access marker interface.
HashMap if for key-vlaue pair and HashSet is for unique items.
 
Ranch Hand
Posts: 2120
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A linkedList performs better than an arrayList if frequent insertions and removals are required. Otherwise use the latter because is faster.
LinkedList is implemented by a doubled-linked list. This makes the insertions and removals inside the list quicker than over the array that supports an arrayList.
Two capabilites for choosing LinkedList over ArrayList:
a) a linkedList can provide a ListIterator. This Iterator is able to go forward and backwards in the list. Also it has the ability to add and replace an item in the list. Standar iterators do not have these posibilities.
b) a linkedList can be treated as a stack or a double-ended queue. Consult the API for more.
Hashtable is supposed to perform slower than HashMap. Maybe because is synchronized by default. You should use HashMap because is the newest class. While HashMap allows null for keys and values, Hashtable does not.
HashSet is a Set. No duplicates allowed. The elements to be stored must provide proper equals and hashcode methods. hashcode method will be called at the time of locating/adding the element to the hashed structure that backs the HashSet. equals will be called to compare for equality with elelements already in the structure -no duplicates allowed--
Because of the use of the hashed structure the HashSet should be quick.
 
bobby chaurasia
Ranch Hand
Posts: 84
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the prompt reply.
As per api for HashMap it says "
"Hash table based implementation of the Map interface"
Similarly for HashSet it says
"This class implements the Set interface, backed by a hash table (actually a HashMap instance). "
What is the implication of these statements ?
 
bobby chaurasia
Ranch Hand
Posts: 84
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I forgot to add this.. what is the difference between Set and HashSet? Both of them implement the Set interface.
Thanks
 
Jose Botella
Ranch Hand
Posts: 2120
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is a dictionary of data structures.
Bobby, you might find interesting the Collections
part of the Java Tutorial.
Also:
Holding your objects chapter 8 from Thinking in Java. Please read this one. It is extraordinary.
[ January 11, 2003: Message edited by: Jose Botella ]
 
author
Posts: 3252
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A few minor details.

Hashtable is supposed to perform slower than HashMap. Maybe because is synchronized by default. You should use HashMap because is the newest class. [...]

IMNSHO, I'd put this a bit more strongly: never, ever, use Hashtable (or Vector) if you don't absolutely have to.
  • The Collections classes form a logical, systematic framework of interfaces and implementations. Vector, Hashtable and Enumeration fall completely outside this framework and do nothing that the framework classes don't do. They are unnecessary baggage, so much extra stuff to remember without benefit.
  • Retrofitting them with the Collections interfaces has made their APIs bloated and inconsistent. What shall I use today, v.iterator() or v.elements()? If you use them in a multi-developer project, inconsistencies will happen.
  • If your code is single-threaded, the synchronization in Vector and friends does nothing for you and just decreases performance.
  • If your code is multi-threaded... the sychronization in Vector and friends still does nothing for you and just decreases performance! You see, most of the time their synchronization is at the wrong level; most of the time, you have composite operations which need to be atomic w.r.t. other threads rather than the little Vector and Hashtable methods.
  • Worse, the synchronization in Vector and Hashtable is likely to lure developers inexperienced in concurrent programming into a false sense of security. "I'm using a threadsafe collection, so my code is threadsafe". D'oh. That's not how it works. As a consequence, code using Vector and Hashtable is in my experience more likely to be thread-unsafe than code using the Collections framework.
  • I know many, many developers still use them, and to me it is a complete mystery why.

    A linkedList performs better than an arrayList if frequent insertions and removals are required. Otherwise use the latter because is faster.

    In addition to the things you mentioned, a LinkedList is very bad at finding an arbitrary element in the middle of the list (i.e. list.get(i)). An ArrayList, on the other hand, is good at inserting or deleting elements at the end of the list but very bad at doing this anywhere else in the list.
    These performance characteristics are often denoted using the big-O notation. This notation tells you how execution time grows as the number of elements (N) in the collection grows. For example, list.get(i) performs O(N) for LinkedList but O(1) for ArrayList, except when i is the start or the end of the list. In other words, for a LinkedList, if the list gets twice as large then list.get(i) will take twice as long on average; for an ArrayList, it the list size won't make any difference whatsoever.

    a) a linkedList can provide a ListIterator.

    So can an ArrayList; in fact, so should any implementation of the List interface, since it is part of the List API.

    As per api for HashMap it says "
    "Hash table based implementation of the Map interface"
    Similarly for HashSet it says
    "This class implements the Set interface, backed by a hash table (actually a HashMap instance). "
    What is the implication of these statements ?

    The implications are for performance and ordering. See below. The second statement essentially says that a HashSet will have the same characteristics as a HashMap.

    I forgot to add this.. what is the difference between Set and HashSet? Both of them implement the Set interface.

    HashSet is an implementation of the Set interface that uses a hash table behind the scenes. This has implications for the kinds of objects you can store and for its performance.
    The objects you store must have correctly working, consistent hashCode() and equals() implementations, otherwise things go badly wrong. See the javadoc for java.lang.Object for more information about this.
    The performance is O(1) for most operations, which means that the time taken to store a new object in the Set, or to check whether the Set contains a specific object, is more or less constant.
    This is significantly better than say, a TreeSet, which has a performance that decreases logarithmically with the number of objects held (O(log(N)) performance). Why would you ever use a TreeSet then? Well, when you iterate over a HashSet you get the elements in an essentially random order which may change every time you modify the set. A TreeSet maintains its elements in sorted order.
    Although not strictly exam material, it extremely useful to be aware of the performance characteristics of the Collection implementation classes. The resources linked to in the previous response are very good sources of information.
    - Peter
    [ January 11, 2003: Message edited by: Peter den Haan ]
     
    Jose Botella
    Ranch Hand
    Posts: 2120
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thank you very much for the additional information, anf for correcting my slip.
    The wrong level synchronization of Vector was very helpful.
    reply
      Bookmark Topic Watch Topic
    • New Topic