Explain the differences between a HashMap and a TreeMap in Java. What are the underlying implementations and when would you use one over the other?

A HashMap implements the Map interface using a hash table, allowing null values and one null key. It offers O(1) time complexity for basic operations like get and put under average load. A TreeMap, on the other hand, uses a Red-Black tree structure, does not allow null keys, and maintains a sorted ordering of its keys, leading to O(log n) time complexity for basic operations. Use HashMap for unsorted collections and when null keys are needed. Use TreeMap for sorted collections, especially if you need to traverse the map in order.