Re: Vector versus Hashtable and Related Questions
On 11/27/2010 1:38 AM, 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."
I haven't read the original (it's a site that wants to me to
register, and I get enough spam already), but the explanation seems
at best approximate and at worst just plain dumb.
I'd also note that the explanation is rather old, and that the
List and Map interfaces (ArrayList and HashMap most likely, in this
context) have pretty much supplanted the older Vector and Hashtable.
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?
<Shrug.> If users.size() is hundreds or thousands, some other
data structure would probably be faster. If users.size() is a half
dozen, sequential search is fine. And in either case, if the search
is only done once a minute it simply doesn't matter.
Also, why use "synchronized" on the findUser method when both Vectors
and Hashtables are already synchronized?
Each individual operation on a Vector is synchronized, but the
search uses multiple operations to look at elements 0,1,2,... It also
uses multiple operations to get users.size(). Those operations are
themselves synchronized, but you need the "composite operation" to be
synchronized and self-consistent. For example, what happens if you
set i=42 and test it against users.size()=43, and before you get around
to inspecting element 42 some other thread deletes it? The users.size()
value you just obtained is no longer correct, and when you try to do
users.get(42) you get an exception.
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.
The object instance "is itself," independently of whatever Vectors
and Hashtables and Lists and arrays and whatnot may happen to hold
references to it. That's the thing to remember: All these containers
and variables and so on hold *references* to objects, not the objects
themselves. Your telephone number resides in N different people's
contact lists; that doesn't mean you have N telephones. If you change
your ring tone, it will sound for all N of those callers.
--
Eric Sosman
esosman@ieee-dot-org.invalid