• Darren (unregistered)

    AHHHH My eyes!!!!!!
    return (tempHt[name] != null)

  • (cs)

    The double parens in the if statement are particularly nice. MUST... PROTECT... THE... IF... CLAUSE... Also it would be bad practice to break out of the loop as soon as you find the element! You must look at every single element just in case the one at the very top isn't really the one you're looking for and the real one is hiding somewhere at the bottom.

  • (cs) in reply to Darren

    Anonymous:
    AHHHH My eyes!!!!!!
    return (tempHt[name] != null)

    er.uumm.. That won't work.  The function in question  returns true is there exist an item whose value is equal to name.  Your returns true is there exist an item whose key is equal to name.

  • (cs)
    Alex Papadimoulis:

    who needs ContainsValue() when you can have isInList()?

    To be fair, ContainsValue is a linear time operation, so perf wise, it's not much better than what is here.  If he was doing a linear scan for a key, that would be a total WTF, but a scanning all the keys for a value is the only way to find if a value is in a one-way associative mapping. That said, there are still some WTFs besides the obvious why not use the built in capability...

      while (en.MoveNext())
  {
    if ((((string)tempHt[en.Key]) == name))
    {
      found = true;
    }
  }
  return found;
}

    The fact that he is enumerating the dictionary (the enumeration gives both keys and values) takes his routine from O(n) to O(n*lg(n)).  "tempHt[en.Key]" is a long and slow way of saying "en.Value".

    The fact that he doesn't return as soon as the value is found is a minor WTF...Short circuiting won't change the algorithmic complexity, but it will cut the average runtime in half for cases where the value exists.

  • Matt B (unregistered)

    Hashtable tempHt = new Hashtable() SystemCache.getProductNames();


    uh isn't this a syntax error?

  • (cs) in reply to pagefault
    pagefault:

    The fact that he is enumerating the dictionary (the enumeration gives both keys and values) takes his routine from O(n) to O(n*lg(n)).  "tempHt[en.Key]" is a long and slow way of saying "en.Value".

    I meant to say the fact that he is enumerating the dictionary and then feeding the key back into the dictionary lookup.  Also, I was thinking in terms of tree-based dictionaries.  Hashtable lookup may not be lg(n), depending on the quality of the hashing function and the contents of the hashtable it could be as good as constant.  Regardless, it is slower than directly accessing the enumerated value.

    (I would have edited the original post, but it said my edit time had expired, less than a minute after I posted)

  • (cs)

    And the next question is, why are we using a hashtable at all?  SystemCache.getProductNames() must return an IEnumeratable collection (a requirement to use it to construct a Hashtable).  Hence this could be reduced to :

    private bool isInList(string name)
{
  foreach (DictionaryEntry de in SystemCache.getProductNames())
      {
           if (de.Value == name)
                 return true;
      }
      return false;
    }

    Since the Hashtable constructor would have to do exactly the same foreach to build the Hashtable, before it could do anything else (e.g. a ContainsValue), this would be the fastest way to deal solve this problem -- assuming that the collection getProductNames return is not itself a Hashtable, in which case it would be just:

    private bool isInList(string name)
{
      return SystemCache.getProductNames().ContainsValue(name);
}

     

  • (cs) in reply to rogthefrog
    rogthefrog:
    You must look at every single element just in case

    What if another thread changes the values somehow?  Better look at the elements twice and check if they have changed...  Maybe three times?  No, better not be wasteful, two is enough times.
  • (cs) in reply to loneprogrammer

    loneprogrammer:
    rogthefrog:
    You must look at every single element just in case

    What if another thread changes the values somehow?  Better look at the elements twice and check if they have changed...  Maybe three times?  No, better not be wasteful, two is enough times.

    The third time is the charm, why not throw in some double locks to avoid threading issues.

  • (cs) in reply to loneprogrammer

    I admit I don't use java much, so I am confused about this part:

    Hashtable tempHt = new Hashtable() SystemCache.getProductNames();

    I understand that a new hashtable is being created, but how does getProductNames()  factor into things? What datatype is returned by getProductNames and what does this particular syntax mean?  Is it a hashtable that is being copied?  Is it a different datatype being cast into a hashtable? 

     

  • (cs) in reply to Matt B
    Anonymous:
    Hashtable tempHt = new Hashtable() SystemCache.getProductNames();

    uh isn't this a syntax error?

    Whoops my mistake ... I really gotta proof read better ... (I slightly transformed the code to protect the submitter and myself)

  • (cs)

    This would be way faster if he distributed the work across five or so worker threads.
    </sarcasm>

  • (cs)

    Shouldn't they be using .equals instead of ==

  • (cs) in reply to Alex Papadimoulis
    Alex Papadimoulis:
    Anonymous:
    Hashtable tempHt = new Hashtable() SystemCache.getProductNames();

    uh isn't this a syntax error?

    Whoops my mistake ... I really gotta proof read better ... (I slightly transformed the code to protect the submitter and myself)

    well, I guess that answers my questions ! 

  • diaphanein (unregistered) in reply to pagefault
    pagefault:

    To be fair, ContainsValue is a linear time operation, so perf wise, it's not much better than what is here.  If he was doing a linear scan for a key, that would be a total WTF, but a scanning all the keys for a value is the only way to find if a value is in a one-way associative mapping. That said, there are still some WTFs besides the obvious why not use the built in capability...

    Even if ContainsValue is linear, creating a Hashtable, assigning the entire list to it and then keying back into the hashtable is greater than an O(n) operation.  (Even if it is linear, it will still be more expensive, both in memory and cpu cycles, than ContainsValue).  In this case, a linear scan would be a superior approach, assuming unordered data.  Or, if this data is not expected to change, caching the hashtable that is constructed could be of benefit.

    The author of this code ought to have considered an alternative container than a list if this sort of keyed access is needed.

  • (cs)

    I bet it'd be faster if it were written in JavaScript.

    (Come on, you knew somebody had to say it.)

  • Anonymous (unregistered) in reply to Jeff S
    Jeff S:

    I admit I don't use java much, so I am confused about this part:



    Probably you don't use a lot of .NET either...
  • (cs) in reply to diaphanein

    Anonymous:
    ContainsValue is linear, creating a Hashtable, assigning the entire list to it

    As recently corrected by Alex, the original code does not create a Hashtable -- it merely stores a reference to it.  It also shows that getProductNames() returns a Hashtable, which mean the second version in my post above is the best.

  • dhromed (unregistered) in reply to FrostCat
    FrostCat:
    I bet it'd be faster if it were written in JavaScript.

    (Come on, you knew somebody had to say it.)


    Client-side javascript of course, using the DOM, that reads the HTML table generated by the .Net from the hashtable, that outputs the data into a form, then submits that form and stores it in a database.

    In a single field.

    Comma-separated.
  • Matt B (unregistered) in reply to whojoedaddy
    whojoedaddy:
    Shouldn't they be using .equals instead of ==


    This is why I love .NET
  • (cs)

    A few things here.  Hashtable performance is O(1) given the hashcodes are well distributed.

    Maybe this is esoteric .NET stuff, but I don't see where a new hashtable is created.  Wouldn't SystemCache return an existing hashtable?  It's not much of a cache if it creates a new Object everytime it's called.

  • (cs) in reply to rogthefrog

    rogthefrog:
    You must look at every single element just in case the one at the very top isn't really the one you're looking for and the real one is hiding somewhere at the bottom.

    "These are not the elements you are looking for. He can go about his business. <!--StartFragment -->Move along."

     

  • (cs) in reply to dubwai

    dubwai:
    Maybe this is esoteric .NET stuff, but I don't see where a new hashtable is created. 

    The code originally posted created a new Hashtable & included a syntax error.  Alex later corrected it.

  • (cs) in reply to JamesCurran
    JamesCurran:

    dubwai:
    Maybe this is esoteric .NET stuff, but I don't see where a new hashtable is created. 

    The code originally posted created a new Hashtable & included a syntax error.  Alex later corrected it.

    Yeah, I figured that out after my post.

  • (cs)

    Okay, forget all my babble about freedom and human rights in the General Discussion thingy. Death by firing squad for writing mind-numbingly bad code!

  • (cs)

    However, if this method is called often, then the choice of data structure is wrong in the first place.

    What would you key product names against, anyway?

  • anon (unregistered) in reply to JamesCurran
    JamesCurran:

    And the next question is, why are we using a hashtable at all?  SystemCache.getProductNames() must return an IEnumeratable collection (a requirement to use it to construct a Hashtable).  Hence this could be reduced to :

    private bool isInList(string name)
    {
      foreach (DictionaryEntry de in SystemCache.getProductNames())
      {
           if (de.Value == name)
                 return true;
      }
      return false;
    }


    Small nit: In C#, this would be incorrect--you need to cast de.Value to a string first, so that it's string's overloaded "==" operator that gets used instead of identity equality.  Either that, or put name on the left.  (In fact, the compiler will warn you about this: "Possible unintended reference comparison; to get a value comparison, cast the left hand side to type 'string'")
  • (cs) in reply to Anonymous
    Anonymous:
    Jeff S:

    I admit I don't use java much, so I am confused about this part:



    Probably you don't use a lot of .NET either...

    uhh ... yeah, I guess not ... I mean, why should invalid code with syntax errors confuse me?  I must be an idiot, huh ?

  • explainator (unregistered) in reply to Jeff S
    Jeff S:
    Anonymous:
    Jeff S:

    I admit I don't use java much, so I am confused about this part:



    Probably you don't use a lot of .NET either...

    uhh ... yeah, I guess not ... I mean, why should invalid code with syntax errors confuse me?  I must be an idiot, huh ?


    ..and you'd notice that it was C# and not Java.
  • Lars Westergren (unregistered) in reply to explainator

    Minor nitpick - Java has both Hashmap and Hashtable, the only difference (that I'm aware of) is that Hashtable is thread safe.

  • Nitpicker (unregistered) in reply to Lars Westergren

    Super minor nitpick: Java has a HashMap (Mind the capital 'M') [:$]

  • (cs) in reply to Lars Westergren
    Anonymous:
    Minor nitpick - Java has both Hashmap and Hashtable, the only difference (that I'm aware of) is that Hashtable is thread safe.


    Hashtable, is the ancient, pre-Collection way of doing it - it's synchronised (so thread-safe), and doesn't allow nulls (unlike HashMap). Hashtable's been retrofitted into the Collections framework, but it still has the elements() method that returns an Enumeration - I don't think these fail-fast if the underlying Hashtable changes, unlike Iterators.

  • deepspace (unregistered)

    I guess just a case of bad API reading, since his implementation is somewhat in the right direction.

    What I did just some time ago, was to use two hashtable, one [key -> value] and one [value -> key]. Finding values is really very fast this way (specially on a mobile device, with about 700 javalines/sec of speed :/ ). A linear search just wasn't an option.

  • deepspace (unregistered)

    I guess just a case of bad API reading, since his implementation is somewhat in the right direction.


    What I did just some time ago, was to use two hashtable, one [key -> value] and one [value -> key]. Finding values is really very fast this way (specially on a mobile device, with about 700 javalines/sec of speed :/ ). A linear search just wasn't an option.

  • CLS (unregistered) in reply to pagefault

    Well, maybe he's worried that another thread may be adding more objects further down in the hashtable while he's scanning the hashtable....  H

  • Justin (unregistered) in reply to Matt B

    Assuming you are saying that .net doesn't differentiate between the two, how do you tell the difference between two different strings with identical content?

    Justin.

  • (cs)

    Well, get used to code like this.

     

    With the increased use of the STL and .NET libraries and the general lack of understanding of the underlying architecture that newer coders have. This will become standard coding practice.

    I must admit, that when I read this code I thought to myself that its not all that bad...

    ...

     

    STOP pelting me with rotten fruit.

    Please understand I am not a C++ or .NET coder and have only the most rudamentory understanding of .net or STL.

     

    It takes some experience of these and the (shudder) "best practices" to see what is wrong.

    Looking at other WTFs they are self evident... this requires a little deeper knowledge.

     

    Not quite as good a wtf as some of the others.

  • Justin (unregistered) in reply to Matt B
    Anonymous:
    whojoedaddy:
    Shouldn't they be using .equals instead of ==


    This is why I love .NET


    Assuming you are saying that .net doesn't differentiate between the two, how do you tell the difference between two different strings with identical content?
  • (cs) in reply to explainator


    ..and you'd notice that it was C# and not Java.

    Again, the original code posted had syntax that was not valid in C#, so I assumed it must be something else. 

  • (cs) in reply to Jeff S

    ... plus I missed the reference to ".NET" in the first line of the posts, too, I guess [:$]

  • Java coder (unregistered)
    Alex Papadimoulis:

    who needs ContainsValue() when you can have isInList()?

    private bool isInList(string name)
    {
      bool found = false;

      Hashtable tempHt = SystemCache.getProductNames();
      IDictionaryEnumerator en = tempHt.GetEnumerator();
      while (en.MoveNext())
      {
        if ((((string)tempHt[en.Key]) == name))
        {
          found = true;
        }
      }
      return found;
    }


    I'm not a C# coder, but the example code I'm looking at seems to be searching for a matching key, while posts here seem to be discussing a search for a matching value.  Did the example change in this regard?  (I see mention of a change, but it didn't seem to indicate a change to this aspect of the code.)

  • (cs) in reply to Java coder

    Anonymous:


    I'm not a C# coder, but the example code I'm looking at seems to be searching for a matching key, while posts here seem to be discussing a search for a matching value.  Did the example change in this regard?  (I see mention of a change, but it didn't seem to indicate a change to this aspect of the code.)

    It appears that C# has overloaded [] to be equivalent to the Map.get() method in Java.  If this is so, it is enumerating over the keys and comparing the associated value with the input.

  • Java coder (unregistered) in reply to dubwai
    dubwai:

    It appears that C# has overloaded [] to be equivalent to the Map.get() method in Java.



    Ah -- now it all makes sense.  Thanks.

    I mean of course, that the dialog here now makes sense.  The sample code clearly rates a WTF posting, primarily because the standard method would be clearer where used.  From a performance standpoint, the iterator over the keys would take at least as long as the iterator over the values (twice as long when the value exists), but you add to that the time to get the hash value for the key and search the linked list for the appropriate hash table entry.   WTF for?

  • (cs) in reply to Justin

    Anonymous:
    Assuming you are saying that .net doesn't differentiate between the two, how do you tell the difference between two different strings with identical content?

    It's not that it doesn't differentiate, it's that string has an overloaded operator==, which is generally an appropriate thing to do on immutable classes with value semantics.

    If you want to tell the difference between different string instances with the same content, first you should ask yourself why you are trying to do that - object identity is rarely the right answer in this situation.  However, if you really want to do it, the simplest way is to compare the strings as objects:

    if ((object)string1 == (object)string2) // strings are the same identical instance

  • (cs) in reply to pagefault
    pagefault:

    if ((object)string1 == (object)string2) // strings are the same identical instance

    Overloaded operators are not polymorphic, I take it.  The more I see how they are used, the more I'm glad I don't have to deal with them.

    How do you do it if you want to see if two Objects are equal polymorphically?  Is there an equals() method on object, like in Java?

  • (cs) in reply to dubwai

    Yes, there is an Equals().

  • (cs) in reply to dubwai

    dubwai:
    Overloaded operators are not polymorphic, I take it. 

    er.umm.. Yes.... That's why string1==string2 is different than (object)string1 == (object)string2

    How do you do it if you want to see if two Objects are equal polymorphically?  Is there an equals() method on object, like in Java?

    Yes, exactly (well, it's called "Equals").  The following C# program should demostrate:

     public static void Main()
     {
      String Str1 = "Hello";
      String Str2 = Console.ReadLine();  // Type "Hello" at Runtime
      Object obj1 = Str1;
      Object obj2 = Str2;
      
      if (Str1 == Str2)
       Console.WriteLine("String == OK");
      
      if ((object) obj1 == (object) obj2)
       Console.WriteLine("Object == OK");
      
      if (obj1.Equals(obj2))
       Console.WriteLine("Equals OK");
     }

    This will print "String == OK" and "Equals OK".  (Typing in one of the string is the simpliest way I could guarentee that the two object were not equal

  • (cs) in reply to JamesCurran
    JamesCurran:

    er.umm.. Yes.... That's why string1==string2 is different than (object)string1 == (object)string2

    Ooops... That's not particularly clear.  That should be "Yes, they are polymorphic"

  • nasch (unregistered) in reply to JamesCurran

    Polymorphic (in my understanding) would mean that the operation depends on the object or run-time type. The example you showed indicates that it depends on the reference or compile-time type. Then again, maybe we're thinking of different definitions of "polymorphic".

  • (cs) in reply to JamesCurran
    JamesCurran:

    Yes, exactly (well, it's called "Equals").  The following C# program should demostrate:

    This will print "String == OK" and "Equals OK".  (Typing in one of the string is the simpliest way I could guarentee that the two object were not equal

    I assume it's not really necessary to cast an Object reference to an object.

Leave a comment on “Not Too Hashish ... err ... Hashlike”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article