algorithm - Proof: why does java.lang.String.hashCode()'s implementation match its documentation? -


The JDK documentation for

says:

The calculation of the hash code for a string object 

  s [0] * 31 ^ (n-1) + s [1] * 31 ^ (n -2) + ... + s [n-1] < Using the / code>  
  int  arithmetic, where  s [i]  is the string of *  i  * of the string ,  N  is the length of the string, and  ^  indicates exponentiation.

The standard implementation of this expression is: 

  int hash = 0; For (int i = 0; i & lt; length; i ++) {hash = 31 * hash + value [i]; } Return hashes;

I feel like I was sleeping through my algorithm course. How does mathematical expression translate into the above code?

I'm not sure if you remember it, "^ ^ Exponentation indicates" But not xor).

Each time the loop is added, the previous value of the hash is added in 31 again before moving forward element of value .

One can prove that these things are equal to induction, but I think an example can be more obvious:

We are saying a 4-four string Let's unlock the loop with: 

  hash = 0; Hash = 31 * hash + value [0]; Hash = 31 * hash + value [1]; Hash = 31 * hash + value [2]; Hash = 31 * hash + value [3];

Now in each statement, by substituting each value of this hash into the following statement: 

  hash = 31 * (31 * (31 * (31 * 0 + value [0]) + value [1]) + value [2]) + value [3]; 31 * 0 is very simple:  
  hash = 31 * (31 * ([31] value [0] + value [1]) + value [2]) + value [3 ];  
 
 Now multiply two internal words by the second 31: 
 
  
 
 Now multiply these three words: 
 
  hash = 31 * 31 * 31 * value [0] + 31 * 31 * value [1] ] + 31 * value [2] + value [3];  
 
 and convert to exponents (not actually Java): 
 
  hash = 31 ^ 3 * value [0] + 31 ^ 2 * value [1] + 31 ^ 1 * value [2] + value [3];

Comments

Post a Comment

Popular posts from this blog

python - Overriding the save method in Django ModelForm -

I'm having trouble overriding a ModelForm save method. I get this error I'm: Exception type: TypeErier Exception Value: Save () found an unexpected keyword argument 'committed' My intentions include a form 3 fields Submit several values ​​for, then create an object for each combination of those areas, and to save each object file models.py class collarsult type (models.Model): id = model. AutoField (db_column = 'icontact_result_code_type_id', primary_key = true) callResult = models.ForeignKey ( 'CallResult', db_column = 'icontact_result_code_id') campaign = models.ForeignKey ( 'campaign', db_column = 'icampaign_id') CALLTYPE = models.ForeignKey ( 'CALLTYPE', db_column = 'icall_type_id') agent = models.BooleanField (db_column = 'bagent', default = true) teamLeader = models.BooleanField (db_column = 'bTeamLeader', default = true) active = models.BooleanField (db_column = Django.form...
Read more

html - CSS autoheight, but fit content to height of div -

I have a div in which there are three children- div in the left and middle div: float: left while true: float: true because it is my layout Actually will spoil, I've used ClearFix Hack: .cf {zoom: 1; }. Cf: First,. Cf: {content: ""; Display: Table; }. Cf: After {clear: both; } It still works, but I want to be the right div an indicator. So it should fill 100% of the parent unit of height. How can I complete this? PS is the full code: & Lt; / Div & gt; & Lt; Div class = "mobile_content" & gt; & Lt; H5 & gt; {{Data.titel}} & lt; / H5> & Lt; Table & gt; & Lt; TR & gt; & Lt; Th & gt; Komponist: & lt; / Th & gt; & Lt; TD & gt; {{Data.komponist}} & lt; / TD & gt; & Lt; / TR & gt; & Lt; TR & gt; & Lt; Th & gt; Instrument: & lt; / Th & gt; & Lt; TD & gt; {{Data.instrumente}} & lt; / TD & gt; & Lt; / TR & gt;...
Read more

qt - How to prevent QAudioInput from automatically boosting the master volume to 100%? -

I have been trying to use Qt5 multimedia to record audio with QAudioInput, however, when I see If QAudioInput is started, it increases the master volume of my sound device to 100%. How can I prevent QAudioInput from changing the master volume? My current development platform is Linux with PalsAdio (with flat audio disabled). How can I use QAudioInput : QAudioDeviceInfo device_info = QAudioDeviceInfo :: defaultInputDevice (); QAudio format format; Format.setSampleRate (44100); Format.setChannelCount (1); Format.setSampleSize (16); Format.setCodec ("Audio / PCM"); Format.setSampleType (QAudioFormat :: SignedInt); Format.setByteOrder (QAudioFormat :: LittleEndian); Std :: cout & lt; & Lt; Device_info.deviceName (). ToUtf8 (). ConstData () & lt; & Lt; Std :: endl; QAudioInput * default_device = new QAudioInput (device_info, format); QIODevice * default_io_device = default_device-> Start (); a QAudioInput.setVolume () method is not you I ...
Read more