What integer hash function are good that accepts an integer hash key?

Knuth’s multiplicative method:

hash(i)=i*2654435761 mod 2^32

In general, you should pick a multiplier that is in the order of your hash size (2^32 in the example) and has no common factors with it. This way the hash function covers all your hash space uniformly.

Edit: The biggest disadvantage of this hash function is that it preserves divisibility, so if your integers are all divisible by 2 or by 4 (which is not uncommon), their hashes will be too. This is a problem in hash tables – you can end up with only 1/2 or 1/4 of the buckets being used.

Related Posts:

  1. hash function for string
  2. waitpid, wnohang, wuntraced. How do I use these
  3. How to initialize array to 0 in C?
  4. Sign extend a nine-bit number in C
  5. Warning: assignment from incompatible pointer type
  6. C: error: expected ‘)’ before ‘;’ token
  7. make: Nothing to be done for `all’
  8. Data argument not used by format strings in C
  9. execv vs execvp, why just one of them require the exact file’s path?
  10. difference between and
  11. expected expression before ‘{‘ token
  12. Setting std=c99 flag in GCC
  13. C Vector/ArrayList/LinkedList
  14. Warning/error “function declaration isn’t a prototype”
  15. Returning an array using C
  16. warning: initializer element is not computable at load time
  17. error: ‘for’ loop initial declarations are only allowed in C99 mode [duplicate]
  18. c – warning: implicit declaration of function ‘printf’
  19. What is a good Hash Function?
  20. Flushing buffers in C
  21. What are 0x01 and 0x80 representative of in C bitwise operations?
  22. How to make parent wait for all child processes to finish?
  23. Undefined Reference issues using Semaphores
  24. What is time(NULL) in C?
  25. Use of cudamalloc(). Why the double pointer?
  26. Portable way to check if directory exists [Windows/Linux, C]
  27. OpenGL — GL_LINE_LOOP —
  28. How to use EOF to run through a text file in C?
  29. Incorrect checksum for freed object on malloc
  30. Valgrind complains with “Invalid write of size 8”
  31. Expression must be a pointer to a complete object type using simple pointer arithmetic
  32. Simple way to check if a string contains another string in C?
  33. What does “request for member ‘*******’ in something not a structure or union” mean?
  34. Segmentation fault (core dumped) due to fgets – I think
  35. C subscripted value is neither array nor pointer nor vector when assigning an array element value
  36. What does “request for member ‘*******’ in something not a structure or union” mean?
  37. Unknown ending signal when using debugger gdb
  38. Valgrind: invalid read of size 4 -> sigsegv, works fine without valgrind and in visual studio
  39. error: too few arguments to function `printDay’ (C language)
  40. How to convert integer to char in C?
  41. Is there a good Valgrind substitute for Windows?
  42. Difference between sizeof(char) and sizeof(char *)
  43. Difference between “move” and “li” in MIPS assembly language
  44. How to empty a char array?
  45. What is the difference between array and enum in C ?
  46. Undefined reference to main – collect2: ld returned 1 exit status
  47. How can one see content of stack with GDB?
  48. What does the term “empty loop” refer to exactly in C and C++?
  49. Is there a way to have printf() properly print out an array (of floats, say)?
  50. Proper way to empty a C-String
  51. malloc(): memory corruption
  52. How do you allow spaces to be entered using scanf?
  53. Excess elements of scalar initializer for pointer to array of ints
  54. X86 assembly – Handling the IDIV instruction
  55. How does one represent the empty char?
  56. Pause screen at program completion in C
  57. Can I define a function inside a C structure?
  58. What is the proper equivalent of “while(true)” in plain C?
  59. Where is the header file on Linux? Why can’t I find ?
  60. Difference between fgets and fscanf?
  61. What is the difference between %g and %f in C?
  62. Why is the sizeof(int) == sizeof(long)?
  63. Structure padding and packing
  64. Lua – Number to string behaviour
  65. How to allocate array of pointers for strings by malloc in C?
  66. Reading in double values with scanf in c
  67. Create your own MD5 collisions
  68. Realloc Invalid Pointer in C
  69. What tools are there for functional programming in C?
  70. typedef fixed length array
  71. “-bash: gcc: command not found” using cygwin when compiling c?
  72. How to format strings using printf() to get equal length in the output
  73. “-bash: gcc: command not found” using cygwin when compiling c?
  74. In C, what exactly happens when you pass a NULL pointer to strcmp()?
  75. lseek/write suddenly returns -1 with errno = 9 (Bad file descriptor)
  76. What are the differences between if, else, and else if? 
  77. Should I use printf(“\n”) or putchar(‘\n’) to print a newline in C?
  78. error: struct has no member named X
  79. strtok segmentation fault
  80. Invalid write of size 1
  81. How to solve static declaration follows non-static declaration in GCC C code?
  82. realloc(): invalid next size when reallocating to make space for strcat on char *
  83. Constructor for structs in C
  84. C Error: declaration shadows a local variable — Won’t let me repeatedly replace the value of my float variable
  85. Sorting an array in C?
  86. MIPS to C Translation
  87. Pointer to 2D arrays in C
  88. Pointer to a string in C?
  89. gdb: No symbol “i” in current context
  90. Cross Platform C library for GUI Apps?
  91. Implicit function declarations in C
  92. Pre increment vs Post increment in array
  93. Convert long long to string in C?
  94. Using pointer to char array, values in that array can be accessed?
  95. How can I create a dynamically sized array of structs?
  96. how to stop a loop arduino
  97. How to normalize a mantissa
  98. Level vs Edge Trigger Network Event Mechanisms
  99. How to use shared memory with Linux in C
  100. When is it ok to use a global variable in C?

Leave a Comment