A high-precision marine gravity gradient reference map is key to enabling underwater gravity gradient matching navigation. At present, the construction of the reference maps is based on quadrilateral geographic grids. However, quadrilateral grids lead to detriangulation at high latitudes, which limits the global applicability of such maps to underwater gravity navigation. To circumvent the limitations of quadrilateral grids, a hexagonal grid is introduced for constructing the reference map. This paper analyzes the characteristics of the icosahedral Snyder equal area aperture 4 hexagon (ISEA4H) and H3 grid systems and selects an appropriate grid system. In addition, we calculate and analyze the grid model errors and matching positioning errors of hexagonal and quadrilateral grids at the same resolution. The experimental results show that the grid model and matching positioning errors of a hexagonal grid system are more than 14% and 15% less than those of a quadrilateral grid system, respectively, indicating the feasibility and effectiveness of applying hexagonal grids to gravity gradient matching navigation. Given the low construction efficiency of a marine hexagonal grid gravity gradient reference map, we propose an efficient CPU+GPU hybrid parallel scheme. A global total tensor marine hexagonal grid gravity gradient reference map model is then constructed.