ScratchAPixel : Understanding how to use Perlin's permutations hash table
First, (1/2) I didn't understand how the hash table is actually used. The workflow I think I understood is the following :
  
  
  For an input (coordinate), we find the both nearest pre-defined coordinates (i.e. : those present as indices in A). It's a multiple of
  255.
  The lower one is used to lookup in B
  We get a number between [0;255] that we use to lookup in A 
  We get a number between [0;1] : the noise.
  
  
  But where is the interpolation between the both pre-defined
  coordinates' noise values ?


There are 4 of most of what you wrote here, then the interpolation. For example, if your 2D input is (2.7, 6.4):


You would truncate that to (2,6).
Then perform the permutation and noise lookup steps for (2,6), (3,6), (2,7), (3,7).
And finally perform a 2D interpolation (lerp) of the 4 lookups with the remainder of your input: (0.7, 0.4).


As for the second part of your question, the table is just a creative way to get a "(int, int) -> int" hashing function to go from input coordinates to an index to pick a value in the random data table. You could use any generic hash function instead. In fact, the method used is fairly obsolete for CPUs as it does not lend itself to SIMD implementation and has horrible memory dependencies. It might still have value for GPUs as they have different behavior. But it will have a visible period of 256 which can cause problems in images. So it is really a poor hash function but for the CPUs back then, it was fast and used little memory which is likely why it was picked.