You would not use a lookup table since this is a simple math operation. This can be done in assembly but you mention C which is simpler still.
There are 2 ways to get your reading. One is you use an external interrupt pin for taking in the pulses. Those interrupts advance a counter. You have a hardware timer set up to go off every half sec or sec and when it does it counts to see how many pulses have happened in that interval. The disadvantage is there may be poor resolution with this strategy, particularly at low pulse rates. It can be improved by extending the sample period. The screen update rate need not be the same as the sample period though. For example, you could collect pulses over a 2 sec interval while still updating the screen every half sec. In this case the code would save a history of how many counts it's seen over the last 4 of the 1/2-sec timer intervals and use that as the basis for the new reading.
The other is the Capture input. It's not available on all PICs. This copies a timer's value when the pulse comes in so it can calculate the time difference between any two pulses with good resolution, provided you have chosen your time periods wisely. The result is immediate and it does not require another timer resource on top of the one it is using as a counter. It does not work well if not all pulses have the same shape since the input may trigger at unpredictable points on the pulse thus rendering the time between them unreliable. Such a case might arise if you had 3 features on the shaft which trigger a Hall effect sensor and they are not all exactly 120 deg apart or even magnetically different from each other so they trigger the sensor at a slightly different phase. In this case taking 3 known sequential samples and averaging them will eliminate the problem.
In either case simple unsigned integer math will be used to generate mph or kph out of the reading.