c++


What would be a good hash function for this list of English words?


Here's my code on Github if anyone would like to see it :
https://github.com/daicain/Hashing-Project
Currently, I am using a tablesize of 80, since I have about 73 words in the file.
My current method of hashing is pretty basic and generic. I add up the ASCII value of the letters after I make them all lowercase, then I mod (%) by the tablesize (80 currently). I am getting a lot of collisions, and a lot of unused bucket/indexes. Since I know exactly which words I need to hash and how many, are there better methods to use, for the least possible collisions? My goal is to get 6 or less.
Also, side question. Once the words are in the hashtable, if I want to look up a certain word, but type that word incorrectly, or scrambled up, how would I find it in the hashtable?
For example, if I have "apple" in the hashtable, and for my search, I use "leppa", which is apple spells backward, whats a good way to unscramble "leppa" in such a way that, apple would come out?
Please ask me if you're unsure about what I just ask, sorry if I'm not clear!
Murmur hash is considered fast and will probably give good distribution
http://en.wikipedia.org/wiki/MurmurHash
In order to look for a "scrambled" text in a hash, you need to use hash-function that is agnostic to the letters order - pretty bad idea since all permutations will be in the same hash bucket
Try md5, you won't have collisions in your dictionary.
You may simply use std::hash:
#include <string>
#include <iostream>
#include <functional>
int main()
{
std::string str = "air conditioner";
size_t h = std::hash<std::string>()(str);
std::cout << "hash of \"" << str << "\" is " << h << std::endl;
}
commonly it might be implemented as fnv1 hash. Another good hash function is murmur. Check related question on stackexchange for other common hash functions.

Related Links

“no matching function” initializing class
Code compiles and links but does not run (at all, loading libraries fails)
Architecture-generic InterlockedIncrement for 32/64-bit
Why do I get garbage value when output character array to console?
How can I prevent my program from closing when a open console window is closed?
How to calculate double variable with 10 decimal precision in C++
why const x is ok when multi include it
Implementation of friend overload << operator with templates
WT save file dialog window?
Run-Time Check Failure #2 - Stack around the variable 'a' was corrupted
Why does this code give me an infinite loop?
Problems pasing a matrix to my method
what happened when function return
use the method of extended class and of derived
PushBack (push_back()) elements of QStringList to vector<string>
Create a class using objects of another class

Categories

HOME
dropbox-api
rabbitmq
appium
uitableview
post
64bit
mapkit
asp.net-web-api2
geogebra
c#-3.0
memcached
codeception
snapshot
webassembly
spring-aop
libreoffice-base
codecvt
jlabel
pixel
sensenet
bit-manipulation
couchbase-view
robots.txt
moshi
sitefinity
footable
autoload
white
magnolia
easymock
smtpclient
960.gs
configuration-files
protactor
safe-browsing
showdown
object-oriented-analysis
jsdoc3
same-origin-policy
satellite
leap-motion
stdio
pubsubhubbub
reportviewer2008
qtquick2
tizen-sdb
java-threads
lunrjs
nibble
user-mode-linux
cts
iterm
couchbase-sync-gateway
rgraph
argo
ssas-2008
gstat
eofexception
jison
rich-snippets
cleartool
orca
mux
stop-words
android-handlerthread
ntl
jform-designer
factoring
socketrocket
application-integration
presentmodalviewcontrolle
node-http-proxy
mat-file
meteor-slides
mib
jquery-ui-selectable
aspnet-regiis.exe
django-staticfiles
enctype
gwt-2.5
fatwire
springmockito
clang-complete
incompatibletypeerror
primefaces-extensions
nsinteger
in-app
cloning
microsoft.build
progressive-enhancement
o3d

Resources

Mobile Apps Dev
Database Users
javascript
java
csharp
php
android
MS Developer
developer works
python
ios
c
html
jquery
RDBMS discuss
Cloud Virtualization
Database Dev&Adm
javascript
java
csharp
php
python
android
jquery
ruby
ios
html
Mobile App
Mobile App
Mobile App