Styjun

Class to generate a pdf invoice

Co-worker is now managing my team. Does this mean that I'm being demoted?

Basic power tool set for Home repair and simple projects

Background for black and white chart

1960s sci-fi anthology with a Viking fighting a U.S. army MP on the cover

Print the phrase "And she said, 'But that's his.'" using only the alphabet

How to search for Android apps without ads?

I have found ports on my Samsung smart tv running a display service. What can I do with it?

Square brackets around a top aligned array

Having some issue with notation in a Hilbert space

How can I maintain game balance while allowing my player to craft genuinely useful items?

How could I create a situation in which a PC has to make a saving throw or be forced to pet a dog?

Why is Skinner so awkward in Hot Fuzz?

Schedule Batch Apex too many rows

How do credit card companies know what type of business I'm paying for?

What are the mechanical differences between Adapt and Monstrosity?

Can you cover a cube with copies of this shape?

Does anyone recognize these rockets, and their location?

What kind of chart is this?

Catching a robber on one line

Leveraging cash for buying car

Why can't I craft scaffolding in Minecraft 1.14?

...and then she held the gun

Numerical second order differentiation

Is there a name for this hash function?

Secure hash and salt for PHP passwordsHow can I generate an MD5 hash?How does a hash table work?How do function pointers in C work?Hash function for short stringsFundamental difference between Hashing and Encryption algorithmsGenerate a Hash from string in JavascriptOpenssl thread-safety-callback-function registration with both direct call and indirect callUnordered Map with three unsigned chars as keyLNK2091 error for OCIObjectGetAttr and OCIObjectSetAttr

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;

4

1

I have used the Elk Scheme interpreter for quite a while and browse its source code sometimes.

I noticed that it contains the following hash function in symbol.c:

int Hash (char const *str, unsigned int len) 
 register int h;
 register char const *p, *ep;

 h = 5 * len;
 if (len > 5)
 len = 5;
 for (p = str, ep = p+len; p < ep; ++p)
 h = (h << 2) ^ *p;
 return h & 017777777777;

There is nothing in the source code that describes the function.

Is there a name for this hash function?

Is the hashing scheme documented somewhere?

c hash

share|improve this question

edited Mar 25 at 4:22

R Sahu

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  That thing is old. I wonder if there's some point where the hash in scheme is visible in scheme code, and they had to keep the old hash.
  
  – Joshua
  Mar 25 at 4:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Joshua, it is used only once in the code base: h = Hash (str, len) % OBARRAY_SIZE; where h is of type int. h is used as an index to an array.
  
  – R Sahu
  Mar 25 at 4:09
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  Looks like it's basically a FNV algorithm with different constants. Odd how it only looks at the first 5 characters...
  
  – Shawn
  Mar 25 at 4:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Unfortunately, the Subversion commit log doesn't contain a useful explanatory message, either.
  
  – Maxpm
  Mar 25 at 4:30
  

  
  
  
  

add a comment | 

4

1

I have used the Elk Scheme interpreter for quite a while and browse its source code sometimes.

I noticed that it contains the following hash function in symbol.c:

int Hash (char const *str, unsigned int len) 
 register int h;
 register char const *p, *ep;

 h = 5 * len;
 if (len > 5)
 len = 5;
 for (p = str, ep = p+len; p < ep; ++p)
 h = (h << 2) ^ *p;
 return h & 017777777777;

There is nothing in the source code that describes the function.

Is there a name for this hash function?

Is the hashing scheme documented somewhere?

c hash

share|improve this question

edited Mar 25 at 4:22

R Sahu

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  That thing is old. I wonder if there's some point where the hash in scheme is visible in scheme code, and they had to keep the old hash.
  
  – Joshua
  Mar 25 at 4:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Joshua, it is used only once in the code base: h = Hash (str, len) % OBARRAY_SIZE; where h is of type int. h is used as an index to an array.
  
  – R Sahu
  Mar 25 at 4:09
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  Looks like it's basically a FNV algorithm with different constants. Odd how it only looks at the first 5 characters...
  
  – Shawn
  Mar 25 at 4:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Unfortunately, the Subversion commit log doesn't contain a useful explanatory message, either.
  
  – Maxpm
  Mar 25 at 4:30
  

  
  
  
  

add a comment | 

I have used the Elk Scheme interpreter for quite a while and browse its source code sometimes.

I noticed that it contains the following hash function in symbol.c:

int Hash (char const *str, unsigned int len) 
 register int h;
 register char const *p, *ep;

 h = 5 * len;
 if (len > 5)
 len = 5;
 for (p = str, ep = p+len; p < ep; ++p)
 h = (h << 2) ^ *p;
 return h & 017777777777;

There is nothing in the source code that describes the function.

Is there a name for this hash function?

Is the hashing scheme documented somewhere?

c hash

share|improve this question

edited Mar 25 at 4:22

R Sahu

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

int Hash (char const *str, unsigned int len) 
 register int h;
 register char const *p, *ep;

 h = 5 * len;
 if (len > 5)
 len = 5;
 for (p = str, ep = p+len; p < ep; ++p)
 h = (h << 2) ^ *p;
 return h & 017777777777;

share|improve this question

edited Mar 25 at 4:22

R Sahu

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

share|improve this question

edited Mar 25 at 4:22

R Sahu

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

asked Mar 25 at 3:55

R SahuR Sahu

173k1299199

1 Answer
1

active

oldest

votes

2

So, it's essentially the same algorithm as the classic Fowler-Noll-Vo hash, but instead of using a specially chosen prime number for the hash's multiplier, it uses 4 (Left shifting a number by 2 is the same as multiplying by 4). The initial seed value of the hash is different too; 5 * len instead of a constant value.

It only hashes up to the first five characters of the string, which is an odd choice that I'm sure the author had some good reason for.

The last line return h & 017777777777; is interesting, too. That octal constant is, assuming a typical 32 bit 2's compliment int, INT_MAX. It's the sort of thing you'd see if calculating a 64 bit hash but returning only the low 32 bits, but on a 32 bit type it's a no-op. Maybe the author was paranoid about portability to systems with a bigger int type? But if it's only used in that one spot where the returned hash value is taken modulo an array length, why bother? Or maybe h was intended to be an unsigned int but they didn't want to use the full range of that type (Or make sure it was never negative when turned into a signed value)?

share|improve this answer

answered Mar 25 at 4:41

ShawnShawn

7,2002616

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The return h & 017777777777; makes sense since the interpreter had been ported to many hardware platforms. It's possible one or more of them used 64 bits for int. I certainly appreciate the forethought.
  
  – R Sahu
  Mar 25 at 4:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  FNV without a prime is no FNV, not that I would expect people to know that. If the caller doesn't do mod prime, this has bad rehash characteristics.
  
  – Joshua
  Mar 25 at 13:22
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55331071%2fis-there-a-name-for-this-hash-function%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

So, it's essentially the same algorithm as the classic Fowler-Noll-Vo hash, but instead of using a specially chosen prime number for the hash's multiplier, it uses 4 (Left shifting a number by 2 is the same as multiplying by 4). The initial seed value of the hash is different too; 5 * len instead of a constant value.

It only hashes up to the first five characters of the string, which is an odd choice that I'm sure the author had some good reason for.

The last line return h & 017777777777; is interesting, too. That octal constant is, assuming a typical 32 bit 2's compliment int, INT_MAX. It's the sort of thing you'd see if calculating a 64 bit hash but returning only the low 32 bits, but on a 32 bit type it's a no-op. Maybe the author was paranoid about portability to systems with a bigger int type? But if it's only used in that one spot where the returned hash value is taken modulo an array length, why bother? Or maybe h was intended to be an unsigned int but they didn't want to use the full range of that type (Or make sure it was never negative when turned into a signed value)?

share|improve this answer

answered Mar 25 at 4:41

ShawnShawn

7,2002616

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The return h & 017777777777; makes sense since the interpreter had been ported to many hardware platforms. It's possible one or more of them used 64 bits for int. I certainly appreciate the forethought.
  
  – R Sahu
  Mar 25 at 4:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  FNV without a prime is no FNV, not that I would expect people to know that. If the caller doesn't do mod prime, this has bad rehash characteristics.
  
  – Joshua
  Mar 25 at 13:22
  

  
  
  
  

add a comment | 

2

So, it's essentially the same algorithm as the classic Fowler-Noll-Vo hash, but instead of using a specially chosen prime number for the hash's multiplier, it uses 4 (Left shifting a number by 2 is the same as multiplying by 4). The initial seed value of the hash is different too; 5 * len instead of a constant value.

It only hashes up to the first five characters of the string, which is an odd choice that I'm sure the author had some good reason for.

The last line return h & 017777777777; is interesting, too. That octal constant is, assuming a typical 32 bit 2's compliment int, INT_MAX. It's the sort of thing you'd see if calculating a 64 bit hash but returning only the low 32 bits, but on a 32 bit type it's a no-op. Maybe the author was paranoid about portability to systems with a bigger int type? But if it's only used in that one spot where the returned hash value is taken modulo an array length, why bother? Or maybe h was intended to be an unsigned int but they didn't want to use the full range of that type (Or make sure it was never negative when turned into a signed value)?

share|improve this answer

answered Mar 25 at 4:41

ShawnShawn

7,2002616

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The return h & 017777777777; makes sense since the interpreter had been ported to many hardware platforms. It's possible one or more of them used 64 bits for int. I certainly appreciate the forethought.
  
  – R Sahu
  Mar 25 at 4:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  FNV without a prime is no FNV, not that I would expect people to know that. If the caller doesn't do mod prime, this has bad rehash characteristics.
  
  – Joshua
  Mar 25 at 13:22
  

  
  
  
  

add a comment | 

So, it's essentially the same algorithm as the classic Fowler-Noll-Vo hash, but instead of using a specially chosen prime number for the hash's multiplier, it uses 4 (Left shifting a number by 2 is the same as multiplying by 4). The initial seed value of the hash is different too; 5 * len instead of a constant value.

It only hashes up to the first five characters of the string, which is an odd choice that I'm sure the author had some good reason for.

The last line return h & 017777777777; is interesting, too. That octal constant is, assuming a typical 32 bit 2's compliment int, INT_MAX. It's the sort of thing you'd see if calculating a 64 bit hash but returning only the low 32 bits, but on a 32 bit type it's a no-op. Maybe the author was paranoid about portability to systems with a bigger int type? But if it's only used in that one spot where the returned hash value is taken modulo an array length, why bother? Or maybe h was intended to be an unsigned int but they didn't want to use the full range of that type (Or make sure it was never negative when turned into a signed value)?

share|improve this answer

answered Mar 25 at 4:41

ShawnShawn

7,2002616

share|improve this answer

answered Mar 25 at 4:41

ShawnShawn

7,2002616

answered Mar 25 at 4:41

ShawnShawn

7,2002616

answered Mar 25 at 4:41

ShawnShawn

7,2002616