I travel a lot on those islands and also used to make my plans at the very last minute. I paid dearly and learned the hard way that it is best to book a car way in advance if for December. Hilo and Kona seem to be particularly tough. True, rental companies overbook, and some people don't show up. But if you try to rent a car as a walk-in at the airport while online reservations show no availability, then typically you end up walking from one rental car window to another - and they either have no availability or have it at astronomical rate. If it's on Oahu then who cares? There are lots of rental cars plus excellent public transportation. But if on the Big Island - then no public transportation, taxi would be very expensive because of the distances, the limited shuttle service that they have has to be reserved weeks in advance. I am not trying to scare you. I am just speaking from experience, I found myself in the same situation several times.