Re: order independent hash?

Discussion in 'Python' started by Dan Stromberg, Dec 5, 2011.

  1. Two methods:
    1) If you need your hash only once in an infrequent while, then save
    the elements in a list, appending as needed, and sort prior to
    hashing, as needed

    2) If you need your hash more often, you could keep your elements in a
    treap or red-black tree; these will maintain sortedness throughout the
    life of the datastructure.

    3) If A bunch of log(n) or n or nlog(n) operations doesn't sound
    appealing, then you might try this one: Create some sort of mapping
    from your elements to the integers. Then just use a sum. This won't
    scatter things nearly as well as a cryptographic hash, but it's very
    fast, because you don't need to reevaluate some of your members as you
    go.

    HTH

    On 11/30/11, Neal Becker <> wrote:
    > I like to hash a list of words (actually, the command line args of my
    > program)
    > in such a way that different words will create different hash, but not
    > sensitive
    > to the order of the words. Any ideas?
    >
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >
     
    Dan Stromberg, Dec 5, 2011
    #1
    1. Advertising

  2. On Monday, December 5, 2011 1:50:08 PM UTC+8, Dan Stromberg wrote:
    > Two methods:
    > 1) If you need your hash only once in an infrequent while, then save
    > the elements in a list, appending as needed, and sort prior to
    > hashing, as needed
    >
    > 2) If you need your hash more often, you could keep your elements in a
    > treap or red-black tree; these will maintain sortedness throughout the
    > life of the datastructure.
    >
    > 3) If A bunch of log(n) or n or nlog(n) operations doesn't sound
    > appealing, then you might try this one: Create some sort of mapping
    > from your elements to the integers. Then just use a sum. This won't
    > scatter things nearly as well as a cryptographic hash, but it's very
    > fast, because you don't need to reevaluate some of your members as you
    > go.
    >
    > HTH
    >

    A sorted list can behave like a hash table. This is of O(log(n)) in accesses
    of n items in theory.

    I agree with you a hash key computation method too slow than a list of n items in accesses for a range of n items should be reloadable.

    But this is not supported in Python yet.

    For tedious trivial jobs of non-heavy computing , I'll opt for easy use.
     
    88888 Dihedral, Dec 5, 2011
    #2
    1. Advertising

  3. On Monday, December 5, 2011 1:50:08 PM UTC+8, Dan Stromberg wrote:
    > Two methods:
    > 1) If you need your hash only once in an infrequent while, then save
    > the elements in a list, appending as needed, and sort prior to
    > hashing, as needed
    >
    > 2) If you need your hash more often, you could keep your elements in a
    > treap or red-black tree; these will maintain sortedness throughout the
    > life of the datastructure.
    >
    > 3) If A bunch of log(n) or n or nlog(n) operations doesn't sound
    > appealing, then you might try this one: Create some sort of mapping
    > from your elements to the integers. Then just use a sum. This won't
    > scatter things nearly as well as a cryptographic hash, but it's very
    > fast, because you don't need to reevaluate some of your members as you
    > go.
    >
    > HTH
    >

    A sorted list can behave like a hash table. This is of O(log(n)) in accesses
    of n items in theory.

    I agree with you a hash key computation method too slow than a list of n items in accesses for a range of n items should be reloadable.

    But this is not supported in Python yet.

    For tedious trivial jobs of non-heavy computing , I'll opt for easy use.
     
    88888 Dihedral, Dec 5, 2011
    #3
  4. On 12/5/11, 88888 Dihedral <> wrote:
    > On Monday, December 5, 2011 1:50:08 PM UTC+8, Dan Stromberg wrote:
    >> Two methods:
    >> 1) If you need your hash only once in an infrequent while, then save
    >> the elements in a list, appending as needed, and sort prior to
    >> hashing, as needed
    >>
    >> 2) If you need your hash more often, you could keep your elements in a
    >> treap or red-black tree; these will maintain sortedness throughout the
    >> life of the datastructure.
    >>
    >> 3) If A bunch of log(n) or n or nlog(n) operations doesn't sound
    >> appealing, then you might try this one: Create some sort of mapping
    >> from your elements to the integers. Then just use a sum. This won't
    >> scatter things nearly as well as a cryptographic hash, but it's very
    >> fast, because you don't need to reevaluate some of your members as you
    >> go.
    >>
    >> HTH
    >>

    > A sorted list can behave like a hash table. This is of O(log(n)) in
    > accesses
    > of n items in theory.
    >
    > I agree with you a hash key computation method too slow than a list of n
    > items in accesses for a range of n items should be reloadable.
    >
    > But this is not supported in Python yet.
    >
    > For tedious trivial jobs of non-heavy computing , I'll opt for easy use.


    A sorted list is O(log(n)) for lookups, but O(n) for insertions. If
    you have a process doing both, the table operations are O(n).

    A hash table that isn't overfilled is O(1) for lookups, O(1) for
    insertions. But this is not ordered.

    Here's a straightforward treap implementation for python, with pure
    python and cython versions:
    http://pypi.python.org/pypi/treap/0.995

    There's also at least one red-black tree implementation available.
     
    Dan Stromberg, Dec 5, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. keksforscher

    Order-independent tags in XML

    keksforscher, Jan 12, 2008, in forum: XML
    Replies:
    2
    Views:
    473
    keshlam
    Jan 13, 2008
  2. rp
    Replies:
    1
    Views:
    595
    red floyd
    Nov 10, 2011
  3. Neal Becker

    order independent hash?

    Neal Becker, Nov 30, 2011, in forum: Python
    Replies:
    5
    Views:
    192
    88888 Dihedral
    Dec 3, 2011
  4. Peter Otten

    Re: order independent hash?

    Peter Otten, Nov 30, 2011, in forum: Python
    Replies:
    49
    Views:
    721
    Lie Ryan
    Dec 11, 2011
  5. Alex Fenton

    Hash#values and Hash#keys order

    Alex Fenton, Apr 7, 2006, in forum: Ruby
    Replies:
    1
    Views:
    162
    George Ogata
    Apr 15, 2006
Loading...

Share This Page