<p>I understand that you want to compute a rolling hash function to hash every n-gram (where n is what you call the "chunk size").  Rolling hashing is sometimes called "recursive hashing". There is a wikipedia entry on the topic:</p>

<p><a href="http://en.wikipedia.org/wiki/Rolling_hash" rel="nofollow">http://en.wikipedia.org/wiki/Rolling_hash</a></p>

<p>A common algorithm to solve this problem is Karp-Rabin. Here is some pseudo-code which you should be able to easily implement in C#:</p>

<pre><code>B←37
s←empty First-In-First-Out (FIFO) structure (e.g., a linked-list)
x←0(L-bit integer) 
z←0(L-bit integer) 
for each character c do
  append c to s
  x ← (B x−B^n z + c ) mod 2^L
  yield x
  if length(s) = n then
     remove oldest character y from s 
     z ← y
  end if 
end for
</code></pre>

<p>Note that because B^n is a constant, the main loop only does two multiplications, one subtraction and one addition. The "mod 2^L" operation can be done very fast (use a mask, or unsigned integers with L=32 or L=64, for example).</p>

<p>Specifically, your C# code might look like this where n is the "chunk" size (just set B=37, and Btothen = 37 ^ n)</p>

<pre><code>r[0] = 0
for (int i=1 ; i &lt; N ; i++) {
    r[i] = a[i] + B * r[i-1] - Btothen * a[i-n];
}
</code></pre>

<p>Karp-Rabin is not ideal however. I wrote a paper where better solutions are discussed:</p>

<p>Daniel Lemire and Owen Kaser, Recursive n-gram hashing is pairwise independent, at best, Computer Speech &amp; Language 24 (4), pages 698-710, 2010.
<a href="http://arxiv.org/abs/0705.4676" rel="nofollow">http://arxiv.org/abs/0705.4676</a></p>

<p>I also published the source code (Java and C++, alas no C# but it should not be hard to go from Java to C#):</p>

<p><a href="https://github.com/lemire/rollinghashjava" rel="nofollow">https://github.com/lemire/rollinghashjava</a></p>

<p><a href="https://github.com/lemire/rollinghashcpp" rel="nofollow">https://github.com/lemire/rollinghashcpp</a></p>
Storing sum of chunks of array through one pass
<p>Let's say I have the array</p>

<pre><code>1,2,3,4,5,6,7,8,9,10,11,12
</code></pre>

<p>if my chunck size = 4 </p>

<p>then I want to be able to have a method that will output an array of ints int[] a = </p>

<pre><code>a[0] = 1
a[1] = 3
a[2] = 6
a[3] = 10
a[4] = 14
a[5] = 18
a[6] = 22
a[7] = 26
a[8] = 30
a[9] = 34
a[10] = 38
a[11] = 42
</code></pre>

<p>note that <code>a[n] = a[n] + a[n-1] + a[n-2] + a[n-3]</code> because the chunk size is 4 thus I sum the last 4 items</p>

<p>I need to have the method <code>without</code> a nested loop </p>

<pre><code> for(int i=0; i&lt;12; i++)
 {
     for(int k = i; k&gt;=0 ;k--)
     {
         // do sumation
         counter++;
         if(counter==4)
           break;
     }
 }
</code></pre>

<p>for example i don't want to have something like that... in order to make code more efficient</p>

<p>also the chunck size may change so I cannot do:</p>

<p><code>a[3] = a[0] + a[1] + a[2] + a[3]</code></p>

<h2>edit</h2>

<p>The reason why I asked this question is because I need to implement check sum rolling for my data structures class.  I basically open a file for reading. I then have a byte array. then I will perform a hash function on parts of the file. lets say the file is 100 bytes. I split it in chunks of 10 bytes. I perform a hash function in each chunck thus I get 10 hashes. then I need to compare those hashes with a second file that is similar. let's say the second file has the same 100 bytes but with an additional 5 so it contains a total of 105 bytes. becasuse those extra bytes may have been in the middle of the file if I perform the same algorithm that I did on the first file it is not going to work. Hope I explain my self correctly. and because some files are large. it is not efficient to have a nested loop in my algorithm.</p>

<p>also the real rolling hashing functions are very complex. Most of them are in c++ and I have a hard time understanding them. That's why I want to create my own hashing function very simple just to demonstrate how check sum rolling works... </p>

<h2>Edit 2</h2>

<pre><code>        int chunckSize = 4;

        int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12 }; // the bytes of the file
        int[] b = new int[a.Length]; // array where we will place the checksums
        int[] sum = new int[a.Length]; // array needed to avoid nested loop

        for (int i = 0; i &lt; a.Length; i++)
        {
            int temp = 0;
            if (i == 0)
            {
                temp = 1;
            }

            sum[i] += a[i] + sum[i-1+temp];

            if (i &lt; chunckSize)
            {
                b[i] = sum[i];
            }
            else
            {
                b[i] = sum[i] - sum[i - chunckSize];
            }

        }
</code></pre>

<p>the problem with this algorithm is that with large files the sum will at some point be larger than int.Max thus it is not going to work....</p>

<p>but at least know it is more efficient. getting rid of that nested loop helped a lot!</p>

<h2>edit 3</h2>

<p>Based on edit two I have worked this out. It does not work with large files and also the checksum algorithm is very bad. but at least I think it explains the hashing rolling that I am trying to explain...</p>

<pre><code>    Part1(@"A:\fileA.txt");
    Part2(@"A:\fileB.txt", null);
</code></pre>

<p>.....</p>

<pre><code>    // split the file in chuncks and return the checksums of the chuncks
    private static UInt64[] Part1(string file)
    {
        UInt64[] hashes = new UInt64[(int)Math.Pow(2, 20)];

        var stream = File.OpenRead(file);


        int chunckSize = (int)Math.Pow(2, 22); // 10 =&gt; kilobite   20 =&gt; megabite  30 =&gt; gigabite etc..
        byte[] buffer = new byte[chunckSize];

        int bytesRead;    // how many bytes where read
        int counter = 0;  // counter

        while ( // while bytesRead &gt; 0
                    (bytesRead =
                        (stream.Read(buffer, 0, buffer.Length)) // returns the number of bytes read or 0 if no bytes read
                    ) &gt; 0)
        {                
            hashes[counter] = 0;

            for (int i = 0; i &lt; bytesRead; i++)
            {
                hashes[counter] = hashes[counter] + buffer[i]; // simple algorithm not realistic to perform check sum of file                    
            }
            counter++;

        }// end while loop     

        return hashes;
    }



    // split the file in chuncks rolling it. In reallity this file will be on a different computer..       
    private static void Part2(string file, UInt64[] hash)
    {            

        UInt64[] hashes = new UInt64[(int)Math.Pow(2, 20)];

        var stream = File.OpenRead(file);

        int chunckSize = (int)Math.Pow(2, 22); // chunks must be as big as in pervious method
        byte[] buffer = new byte[chunckSize];

        int bytesRead;    // how many bytes where read
        int counter = 0;  // counter

        UInt64[] sum = new UInt64[(int)Math.Pow(2, 20)];

        while ( // while bytesRead &gt; 0
                    (bytesRead =
                        (stream.Read(buffer, 0, buffer.Length)) // returns the number of bytes read or 0 if no bytes read
                    ) &gt; 0)
        {

            for (int i = 0; i &lt; bytesRead; i++)
            {
                int temp = 0;
                if (counter == 0)
                    temp = 1;

                sum[counter] += (UInt64)buffer[i] + sum[counter - 1 + temp];

                if (counter &lt; chunckSize)
                {
                    hashes[counter] = (UInt64)sum[counter];
                }else
                {
                    hashes[counter] = (UInt64)sum[counter] - (UInt64)sum[counter - chunckSize];
                }
                counter++;                    
            }



        }// end while loop

        // mising to compare hashes arrays
    }
</code></pre>