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

Why does this double mutex lock not cause deadlock?
Helper function declaration outside class?
Auto declaration of map iterator error on GCC
Finding the length of a C style char * string in c++ [duplicate]
How to draw square on the button at the center using OpenGL?
How to use pthread to write a C++ class like “boost::shared_mutex”
Undefined reference to a superclass' virtual function
How many ways can fill in HxW rooms with 2x1 tatami mats? [closed]
CMake add_subdirectory not invoking the child CMakeLists.txt
How to explicitly get linear indices from arrayfire?
cppunit throws std::bad_alloc after upgrading gcc to 5.4.0
Program compiles but I think switch is ignored.
multiplication of two integer arrays
get and set Enum variable inside a class?
How to use make “using” keyword within a method to accept it as class level
std::array-like class copy constructor

Categories

HOME
gradle
processing
highcharts
inno-setup
firmware
properties
payment
wildfly
fiware
scenekit
powerbuilder
bootstrap-datepicker
binary
visual-foxpro
datagrid
netfilter
apostrophe-cms
jspdf
double
sql-azure
photon
video.js
pentaho-spoon
border
accurev
.net-4.5
stackdriver
multiline
angle
uppaal
polymer-starter-kit
master-detail
vim-syntax-highlighting
webm
openfiledialog
cloudfoundry-uaa
uisegmentedcontrol
submenu
toml
android-auto
notnull
fancytree
laravel-excel
ole
http-status-code-415
cakephp-2.x
tableau-public
rufus-scheduler
measurement-studio
opensmtpd
graylog
dependency-properties
schemaless
kubernetes-health-check
turtle-rdf
pubsubhubbub
nested-function
nokia
website-deployment
arrangeoverride
rgraph
youtube-javascript-api
realbasic
tess-two
android-context
qubole
mpi4py
zipcode
er-diagrams
jaggery-js
linux-capabilities
swift-protocols
tokumx
stacked-area-chart
tracker
ntl
n-tier
start-stop-daemon
impactjs
resourcedictionary
craftyjs
stackmob
circular-reference
mic-1
agi
ldapconnection
customvalidator
trusted-timestamp
static-array
in-app
django-generic-views

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