Re: Vector versus Hashtable and Related Questions
Russ wrote:
Hello All,
This question has been probably "hashed" over many times and googling
the question did answer the question on one hand but also raised
others.
The initial question is: Is a Vector or Hashtable efficient for
searching for clients in say a server to deliver a message? Looking at
this link:
http://www.devx.com/tips/Tip/25941
It says: "Searching through a Vector is O(n), which means that given n
elements, you may have to look at every element before finding what
you are looking for. Unless you use a value as its own key, a
Hashtable will be equally poor."
However that "Unless" creates questions, because looking at some old-
school code (Java 1) from an open-source server where the coder (who
has far more skill than myself) wrote the following method where
"users" is a Vector:
synchronized VUser findUser(String name) {
for (int i = 0; i < users.size(); i++) {
VUser user = (VUser) users.elementAt(i);
if (user.name.equals(name)) {
return user;
}
}
return null;
}
Why did the coder do it that way? Isn't "users" as a Hashtable more
efficient?
Depends. First of all, there is no need to always code things in the
most time-efficient way.
If there are a lot of attributes to search by, it may be simpler to put
the elements in an ArrayList (current successor to Vector) and linear
search rather than maintaining a HashMap (current successor to
Hashtable), for each key.
Computational complexity is a measure of performance in the limit, as
the number of elements tends to infinity. Searching an ArrayList has
less overhead before the first element is examined than searching a
HashMap. If the expected number of users is small, the linear structure
may be faster.
synchronized VUser findUser(String name) {
VUser user = (VUser) users.get( name );
return user;
}
....
Also, why use "synchronized" on the findUser method when both Vectors
and Hashtables are already synchronized?
I don't see the need for synchronization at this level, but I do think
findUser needs to be synchronized to prevent changes in the Vector
during the search. This the reason why Vector-style synchronization is
less useful than it looks, and ArrayList is not synchronized. Many uses
of collections require groups of operations, such as a complete scan, to
be done without changes to the underlying structure.
Finally, suppose I create an instance of a class and put that instance
in two different Hashtables
or Vectors. If I change a variable in that instance in one Hashtable
won't the same instance in the other Hashtable be changed or updated
as well? Common sense says it is the same allotment of memory so yes,
but I am just trying to be certain.
Which reference is used to access an object has no effect on the
contents of the object.
Patricia