How to Get a Hash Value by Numeric Index

How to get a hash value by numeric index

h = {:a => "val1", :b => "val2", :c => "val3"}
keys = h.keys

h[keys[0]] # "val1"
h[keys[2]] # "val3"

How to get the index of a key in a hash?

Hashes aren't usually treated as ordered structures, they simply have a list of keys and values corresponding to those keys.

It's true that in Ruby hashes are technically ordered, but there's very rarely an actual use case for treating them as such.

If what you want to do is find the key corresponding to a value in a hash, you can simply use the Hash#key method:

hash = { a: 1, b: 2 }
hash.key(1) # => :a

I suppose you could use hash.keys.index(hash.key(1)) to get 0 since it's the first value, but again, I wouldn't advise doing this because it's not typical use of the data structure

How to use result from a hash function to get an array index?

Use the remainder/modulo operator % to wrap a randomly-generated value within a certain bound.

If you have 18 elements (indices 0 to 17), you could get an index with 99162322 % 18 (16).

If the number of hash value is not a multiple of the number of indices, the result will be biased. For example, if your hash value is one of the five values from 0 to 4, but you were mapping it onto the three indices from 0 to 2, it would be biased towards 0 (0 % 3, 3 % 3) and 1 (1 % 3 or 4 % 3) over 2 (only 2 % 3). Depending on your needs, the bias may be acceptable if the number of hash values is sufficiently larger than the number of indices. If you want to to avoid it you'll need a scheme to generate a new hash input if the hash result is from the bias-inducing range. Something like this:

function hashIndex(string, length, hashValueCount) {
  var minBiasedIndex = hashValueCount - (hashValueCount % length);
  for (var i = 0; ; i++) {
    var hashInput = string + ":" + String(i);
    var hashResult = hash(hashInput);
    if (hashResult < minBiasedIndex) {
      return hashResult % length;
    }
  }
}

How to calculate an array index from a hash

You could use the remainder operator (%) to map your hash code to an index of an array :

int index = obj.getHashCode ("SomeString") % yourArray.length;

Of course, you should be able to handle clashes (i.e. situations in which two or more Strings are mapped to the same array index).

HashMap handles such potential clashes by storing in each index of the array an entry instance that can point to the next entry that was mapped to that same index (thus forming a linked list).

EDIT:

As was correctly commented below, the % operator wouldn't work for negative hash codes. As an alternative, you can use Math.floorMod (introduced in Java 8) instead :

int index = Math.floorMod (obj.getHashCode ("SomeString"), yourArray.length);

This is guaranteed to return a non-negative index, regardless of the sign of the hash code.

Or you can take the alternative used in HashMap implementation. If the length of your array is always a power of 2, you can use obj.getHashCode ("SomeString") & (yourArray.length - 1).

Create a hash out of an array where the values are the indices of the elements

I'm adding my two cents:

array = [1,3,4,5,6,6,6,8,8,8,9,7,7,7]

hash = {}
array.map.with_index {|val, idx| [val, idx]}.group_by(&:first).map do |k, v|
  hash[k] = v[0][1] if v.size == 1
  hash[k] = v.map(&:last) if v.size > 1
end

p hash #=> {1=>0, 3=>1, 4=>2, 5=>3, 6=>[4, 5, 6], 8=>[7, 8, 9], 9=>10, 7=>[11, 12, 13]}

It fails with duplicated element not adjacent, of course.

This is the expanded version, step by step, to show how it works.

The basic idea is to build a temporary array with pairs of value and index, then work on it.

array = [1,3,4,5,6,6,6]

tmp_array = []
array.each_with_index do |val, idx|
  tmp_array << [val, idx]
end
p tmp_array #=> [[1, 0], [3, 1], [4, 2], [5, 3], [6, 4], [6, 5], [6, 6]]

tmp_hash = tmp_array.group_by { |e| e[0] }
p tmp_hash #=> {1=>[[1, 0]], 3=>[[3, 1]], 4=>[[4, 2]], 5=>[[5, 3]], 6=>[[6, 4], [6, 5], [6, 6]]}

hash = {}
tmp_hash.map do |k, v|
  hash[k] = v[0][0] if v.size == 1
  hash[k] = v.map {|e| e[1]} if v.size > 1
end

p hash #=> {1=>1, 3=>3, 4=>4, 5=>5, 6=>[4, 5, 6]}

It can be written as one line as:

hash = {}
array.map.with_index.group_by(&:first).map { |k, v| v.size == 1 ? hash[k] = v[0][1] : hash[k] = v.map(&:last) }
p hash

Get index of hash with hash key

Try this:

index = @highscore.keys.find_index(player.id)

But, since it looks like you're going to walk the @highscore hash in its sorted by score order, you could just use with_index

@highscore.each.with_index(1) do |(player_id, score), position|
    # use the block variables as you see fit
end

The 1 passed to with_index makes the position start from 1 and not the default 0, which might be what you need.

is it possible to get the Numeric index of url hash?

Replace all your code with:

jQuery(function( $ ){ // DOM ready and $ alias secured

   // other DOM ready code here.........

   // Now, the 3 lines I promised earlier:
   var idx = window.location.hash.replace(/\D/g,'') - 1;
   $(".slides").find('.dslc-modules-area').addClass('hide').eq(idx).removeClass('hide');
   $(".slidelinks li strong").removeClass('active').eq(idx).addClass('active');

});

Also, you logic is quite odd. You don't need two classes .hide and .show. Only one. Think about it.

To recap, to get the index 0..n you can use window.location.hash.replace(/\D/g,'') - 1; where /\D/g is a regex that replaces globally all \D non-digit characters occurrences with '' (so it removes them). So "#1" becomes "1"-1 which is index 0;

Hash-table - Mapping a hash value to an index

You will need to resize the table at some point. Depending on the method you use, you will either need to rehash all keys during the resize-and-copy operation or use some form of dynamic hashing, such as extendible hashing or linear hashing.

As to answering the first part of the question, as you have a used a prime number for the modulo, you should be able to just use the hash value modulo table size to get an index (for a 64-bit int and a table of size 2^16, that would be just the 16 least significant bits of your 64-bit hash). As for the table size, you choose a size that is big enough to hold all data plus some spare room (a value of 0.75 load is used in practice). If you expect a lot of inserts, you will need to give more headroom otherwise you will be resizing the table all the time. Note that with the dynamic hashing algorithms mentioned above this is not necessary, as all resizing operations are amortized over time.

Also, remember that two items can be stored in the same bucket (at the same hashed location in the hash table), the hash function merely tells you where to start looking. So in practice, you would have an array of entries at each location of your hashtable. Note that this can be avoided if you use open addressing to handle hash collisions.

Of course, sometimes you can do better if you choose a different hash function. Your goal would be to have a perfect hash function for each size of your table (if you allow rehashing upon resizing), using something like dynamic perfect hashing or universal hashing.

Hashing for array indices

You may want to have a look at this list of hash functions.

For implementing a hash table (which is your goal I suppose) you'd want a hash function with avalanche effect to avoid too many hash collisions for similar input values.

Of course, you could use any function to turn your characters into an arbitrary integer representation, but if this representation does not vary for different inputs you effectively have the performance of a linked list (imagine using one of the other suggestions with a table size of 256 and none of the structs varies on byte 4). What is your concern about 32-bit hashes? Of course you would use hash%tablesize for indexing?

Normally you wouldn't use a cryptographic hash function (e.g. md5, sha-1) either. Just pick one of the non-cryptographic hash functions (e.g. Pearson/Jenkins hash).

/* jenkins hash, copied from http://en.wikipedia.org/wiki/Jenkins_hash_function */
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
  uint32_t hash, i;
  for(hash = i = 0; i < len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

Side note: When you have a good hash value distribution, also make sure that the size of the hash table is large enough. You will observe performance to degrade as the occupancy (load factor) of the array approaches 1, because the likelihood of hash collisions will increase.

---

Related Topics